LeetCode
思路
递推,动态规划
F(n)
表示爬到第n个台阶
时的方案数
,有多少种方法可以爬上去。
递归
题解
动态规划
typescript
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
if(n === 1) return 1
// 下标表示n阶,值为方法数
const dp = [1, 1]
for(let i = 2; i <= n; i++){
dp[i] = dp[i - 1] + dp[i - 2]
}
return dp[n]
};
优化,利用
滚动数组思想
把空间复杂度优化为O(1)
typescript
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
if(n < 2 ) return 1
let dp0 = 1
let dp1 = 1
// 不用数组,用两个指针临时存,向右移动
for(let i = 2; i <= n; i++){
let temp = dp0
dp0 = dp1
dp1 = dp1 + temp
}
return dp1
};
递归
typescript
// 会超时的递归代码
var climbStairs = function(n) {
function dfs(i) {
if (i <= 1) { // 递归边界
return 1;
}
return dfs(i - 1) + dfs(i - 2);
}
return dfs(n);
};
// 超时~~
// 时间:O(2^n)
// 空间:O(n) 栈空间
优化 初始化 memo存状态
typescript
var climbStairs = function(n) {
let memo = Array(n + 1).fill(0)
function dfs(i) {
if (i <= 1) { // 递归边界
return 1;
}
// 计算过的不用计算了
if(memo[i]){
return memo[i]
}
return memo[i] = dfs(i - 1) + dfs(i - 2);
}
return dfs(n);
};