QA: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
- 总方法数:d[i]=di-1+dI-2
- 边界1:第一次从0阶梯走到1阶梯的方法只能是1种,即1步,所以d[1]=1
- 边界2: 从例子给出d[2]=d[2-1]+d[2-2]=2,得出d[2-2]=d[2]-d[2-1],即d[0]=d[2]-d[1]=2-1=1,所以d[0]=1
时间复杂度O(n)
动态规划
可以使用递归来处理,但递归会消耗内存。
同样将问题分割个多个块,独立处理小的块,再合并处理大的块。
var climbStairs = function(n) {
const d = []
d[0] = 1
d[1] = 1
for(let i = 2; i <= n; i++) {
d[i] = d[i-1] + d[i-2]
}
return d[n];
}
climbStairs(5)
0=1,1=1
2=2
3=3
4=5
5=8
滚动数组思想:
var climbStairs = function(n) {
let p = 0, q = 0, r = 1;
for(let i = 1; i <= n; i++) {
p = q;
q = r;
r = p + q;
}
return r;
}
将值向前推动
q,p,r
0,0,1
0,1,1
1,1,2
1,2,3
2,3,5
3,5,8
…