不要尝试去使用暴力破解,因为即使可能行得通,但通常也会受制于空间和时间的复杂度。
限制条件:一个数组、取不相邻的元素
取多少个,m个,不确定。是不是要取最多个?不确定。
不过有一点能够确定的是,第一个需要取的元素肯定是在第一个和第二个中间、最后一个需要取的元素肯定是在最后一个和倒数第二个。
好,从哪里开始?我们需要一个方向,一个基准点,不如从第一个需要取的元素开始。
第一个可能取的元素可能是a1、a2,假定我们第一个元素取a1。
那么第二个应该取的元素可能是a3~am。假定第二个取的元素时a3。
那么第三个应该取的元素可能是a5~am
... ...
你可能看到了,陷入了暴力枚举的路径了。
那么不如我们换个方向,从最后一个需要的确定的元素开始。
这里有一个区别,我们需要明确,当你确定了最后一个元素时,那么你的方案就完成了。
最后一个需要取的元素可以是 an-1 或 an,我们以 f(n) 来表示每一种可能的方案,那么我们的取数方案就是f(n) + f(n-1)。
好了,到此为止,我们得到了一个可以表示的结果:f(n) + f(n-1)。
是不是很熟悉,具体的算法方案,不再赘述,可以参考:台阶很高,青蛙跳不跳?
每层的最大元素,这是一个竖向遍历,横向对比的查找过程。或者更形象的,就像圣诞树上的环绕的彩带一般。
BFS:广度优先搜索。
1、存储每层找到的最大元素的容器。2、存储每层元素的容器,作为下一层的入口。