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

题目要求

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

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

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

示例 1：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。

  • 支付 15 ，向上爬两个台阶，到达楼梯顶部。
    总花费为 15 。

示例 2:
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。

  • 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
  • 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
  • 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
  • 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
  • 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
  • 支付 1 ，向上爬一个台阶，到达楼梯顶部。
    总花费为 6 。

动态规划

动规五部曲

  1. 确定dp数组（dp table）以及下标的含义
    dp[i] 表示从第i个台阶到达楼梯顶部的最小花费。

  2. 确定递推公式
    dp[i] = min(dp[i-1], dp[i-2]) + cost[i]

  3. dp数组如何初始化
    dp[0] = cost[0], dp[1] = cost[1]

  4. 确定遍历顺序
    从左到右遍历

  5. 举例推导dp数组
    示例1：

    i 0 1 2
    cost[i] 10 15 20
    dp[i] 10 15 30

    示例2：

    i 0 1 2 3 4 5 6 7 8 9
    cost[i] 1 100 1 1 1 100 1 1 100 1
    dp[i] 1 100 2 3 3 103 4 5 104 6 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        if (cost.length == 2) return Math.min(cost[0], cost[1]);
        int[] dp = new int[cost.length];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < cost.length; i++) {
            dp[i] = Math.min(dp[i-1], dp[i-2]) + cost[i];
        }
        return Math.min(dp[cost.length-1], dp[cost.length-2]);
    }
}

代码随想录

在第i阶台阶处不需要消耗费用，只有往上跳了才需要消耗费用
到达第i阶的费用等于从i-1和i-2阶跳上来的最小费用加上跳跃处消耗的费用

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        if (cost.length == 2) return Math.min(cost[0], 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];
    }
}