动态规划
解题思路
确定 dp 数组以及下标的含义：dp[i] 的含义为 跳到第 i 阶台阶有 dp[i] 种方法；
确定递推公式：状态转移方程为
dp[i] = dp[i - 1] + dp[i - 2]：
- 跳到第一阶台阶有 1 种方法，跳到第二阶台阶有 2 种方法，由于 🐸 一次可以跳 一阶台阶 或 两阶台阶 ，则跳到第三阶台阶可以从 一阶 或者 二阶 跳上来，则
dp[3] = dp[2] + dp[1]；- 所以状态转移方程为
dp[i] = dp[i - 1] + dp[i - 2]；如何初始化 dp 数组：由于是从第一阶台阶开始跳，则初始化 dp 数组从 1 开始才有意义：
- 跳到第一阶台阶有一种方法：
dp[1] = 1；- 跳到第二阶台阶有两种方法：
dp[2] = 2；确定遍历顺序：根据递推公式得知，dp[i] 为前面 dp[i - 1]、dp[i - 2] 的和，所以是从前向后遍历；
举例推导 dp 数组：
第 i 阶台阶 1 2 3 4 5 6 7 8 9 10 跳到第 i 阶台阶有 dp[i] 种方法 1 2 3 5 8 13 21 34 55 89
复杂度
-
时间复杂度：
O(n)，循环执行 n 次，每次花费常数的时间代价； -
空间复杂度：
O(1)，只用了常数个变量作为辅助空间；
代码实现
JavaScript
JavaScript
// 递归，空间复杂度 O(n)
var helper = function (memo, n) {
if (n <= 2) return n;
// 备忘录
if (memo[n]) return memo[n];
memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
return memo[n];
}
var climbStairs = function (n) {
return helper([], n);
};
// 迭代，空间状态压缩，空间复杂度 O(1)
var climbStairs = (n) => {
if (n <= 1) return n;
const dp = [];
dp[1] = 1;
dp[2] = 2;
for (let i = 3; i <= n; i++) {
let sum = dp[1] + dp[2];
dp[1] = dp[2];
dp[2] = sum;
}
return dp[2];
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 509. 斐波那契数
上一篇
评论
