动态规划
解题思路
确定 dp 数组以及下标的含义：dp[i] 的含义为 爬到第 i 阶台阶的最低花费；
确定递推公式：
dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]；
- 每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯；
- 可以理解为有两个途径得到 dp[i] ，一个是 dp[i-1] 一个是 dp[i-2] ，对 到达前两个台阶的花费 取最小值，还要加上当前的花费 cost[i]；
如何初始化 dp 数组：可以选择从 0、1 开始向上爬楼梯，则
dp[0] = cost[0]; dp[1] = cost[1]；确定遍历顺序：根据递推公式得知，求出 dp[i] 之前要对比 dp[i - 1]、dp[i - 2] 哪一个花费比较小，所以是从前向后遍历；
举例推导 dp 数组：
索引 i 1 2 3 4 5 6 7 8 9 10 cost[i] 1 100 1 1 1 100 1 1 100 1 爬到第 i 阶台阶的最低花费 1 100 2 3 3 103 4 5 104 6
复杂度
-
时间复杂度：
O(n)，循环执行 n 次，每次花费常数的时间代价； -
空间复杂度：
O(1)，只用了常数个变量作为辅助空间；
代码实现（状态压缩）
var minCostClimbingStairs = function (cost) {
const dp = [];
dp[0] = cost[0];
dp[1] = cost[1];
for (let i = 2; i < cost.length; ++i) {
let dpi = Math.min(dp[0], dp[1]) + cost[i];
dp[0] = dp[1];
dp[1] = dpi;
}
return Math.min(dp[0], dp[1]);
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 70. 爬楼梯
上一篇
评论
