leetcode 746. 使用最小花费爬楼梯

---

---

题目

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/min-cost-climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思考

• 1、遍历是有前后关系的，所有定位到动态规划的方法
• 2、动态规划五步骤
  1、dp[i]的意义
  2、递推公式
  3、初始化
  4、遍历顺序

代码和注释

/**
    动态规划
    1、dp[i]的意义
    2、递推公式
    3、初始化
    4、遍历顺序
 */
class Solution {
    // i表示的是每上一层我们需要的花费
    // 递推公式
    // dp[i] = min(dp[i - 1] + cost[i - 1] , dp[i - 2] + cost[i - 2])
    // 代表的是在当前阶，我前面已经花费的值和上来的值，所以要+cost
    public int minCostClimbingStairs(int[] cost) {
        // 定义动态数组(+1是因为我要的是跃到最上面的结果)
        int[] dp = new int[cost.length + 1];
        // 初始化
        dp[0] = 0;
        dp[1] = 0;
        // 遍历顺序
        for(int i = 2; i <= cost.length; i++){
            dp[i] = Math.min(dp[i - 1] + cost[i - 1] , dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.length];

        

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

总结

• 1、递推公式确实是比较难
  • 这题的想法：dp[i] 是哪里来的
  • 是通过前面走一阶上来的 dp[i - 1] + cost[i - 1]
  • 是通过前面走两阶阶上来的 dp[i - 2] + cost[i - 2]

注意你一定要想清楚我们dp[i]的意思，这里表示每阶我们要花费的值大小