有一个共N级的台阶，一次可以走1级或者2级，问从平地上出发到最高点有多少中走法。
分析： 从终点来看，其走法为倒数一级的走法加上倒数两级的走法。
记f(n) 为到第n级台阶的走法，
则得到DP方程： f(n) = f(n-1)+f(n-2);
初始值有：
f(0) = f(1) = 1
发现就是一个菲波那切数列。。
则代码为：
function res(n) {
let arr = [];
arr[0] = 1;
arr[1] = 1;
for(let i = 2; i<=n; i++) {
arr[i] = arr[i-1] + arr[i-2];
}
return arr[n];
}
但其实没必要用一个数组来记录之前的值，可以只记录前两个值，将空间复杂度由O(n)降到O(1)， 代码如下：
function result(n) {
let a= 1;
let b = 1;
for(let i = 2; i <= n; i++) {
[a, b] = [b, a+b];
}
return b;
}
网友评论