问题
有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法
方案
递归
function getResultByRecursion(n){
if (n < 1) {
return 0;
}
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
return getResultByRecursion(n - 1) + getResultByRecursion(n - 2);
}
console.log(getResultByRecursion(10)) //89
时间复杂度为2的n次方
备忘录算法
let catchData = {}; //缓存已经计算过的步法
function getResultByMap(n){
if (n < 1) {
return 0;
}
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
if (catchData[n]) {
return catchData[n];
} else {
const value = getResultByMap(n - 1) + getResultByMap(n - 2);
catchData[n] = value;
return value;
}
}
console.log(getResultByMap(10)) //89
时间复杂度和空间复杂度都为O(n)
动态规划 （从底向上）
function getResultByDP(n){
if (n < 1) {
return 0;
}
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
let a = 1;
let b = 2;
let temp = 0;
for (let i = 3; i < n + 1 ; i++) {
temp = a + b;
a = b;
b = temp;
}
return temp;
}
console.log(getResultByDP(10)) //89
时间复杂度为O(n)，空间复杂度为O(l)
