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

题目描述

数组的每个索引作为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。

每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。

您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。

1
2
3
4
5
6
7
8
9
10
11

示例 1:

输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。

 示例 2:

输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。

注意：

1. cost 的长度将会在 [2, 1000]。
2. 每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。

算法 ：动态规划

• 假设数组cost长度为n , 则 n个阶梯分别对应下标0到n - 1 ，楼层的顶部对应下标n , 问题等价于计算达到下标n 的最小花费。可以通过动态规划求解
• 初始化 ： 创建长度为 n + 1 的数组dp
• 状态定义 ： 其中dp[i] 表示达到下标i的最小花费
  • 由于可以选择下标为0或者1作为初始阶梯，因此有dp[0] = dp[1] = 0
• 状态转移 ：
  • 当 2 <= i <= n时，可以从下标 i - 1 使用 cost[ i - 1] 的花费达到下标 i
  • 也可以从下标 i - 2 使用 cost[ i - 2] 的花费达到下标 i
  • 故 dp[i] = min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2])
• 返回值 : 最终得到的dp[n] 即为达到楼层顶部的最小花费

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;

        // 1. 初始化
        int[] dp = new int[n + 1];

        // 2. 状态定义
        dp[0] = 0;
        dp[1] = 0;

        // 3. 状态转移
        for(int i = 2;i <= n;i++){
            dp[i] = Math.min(cost[i - 1] + dp[i - 1],cost[i - 2] + dp[i - 2]);
        }

        // 4. 返回值 
        return dp[n];
    }
}

复杂度分析

• 时间复杂度 ： O（n）
• 空间复杂度 ： O（n）

算法 ： 动态规划 + 滚动数组

• 上述代码的时间复杂度和空间复杂度都是 O(n)。

• 注意到当 i >= 2 的时候，dp[i] 只和 dp[i - 1] 和 dp[i -2]有关，因此可以使用滚动数组的思想，将空间复杂度降到O(1)