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 。

提示：

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

动态规划，数组递推

dp[i] 表示到达第 i 级台阶的最小花费，前两个位置初始化为 0，因为从地面开始，不需要花费，从 i=2 开始计算每一级台阶的最小花费，返回到达楼顶的最小花费。

注意，假设数组长度是2，则楼梯顶部是第三个台阶。且可以从0或1开始爬。

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length; // 获取楼梯的阶数
        // dp[i] 表示到达第 i 级台阶的最小花费。注意我们需要的是到达第n级而不是第n-1级台阶的最小花费。第n级才是楼梯顶。
        // 就好像闭区间[0,n]，我们要计算dp[n]。
        int[] dp = new int[n + 1];

        // 初始化 dp 数组，前两个位置初始化为 0，因为题目说你可以选择从下标为 `0` 或下标为 `1` 的台阶开始爬楼梯。重点。
        dp[0] = dp[1] = 0;

        // 从 i=2 开始计算每一级台阶的最小花费
        for (int i = 2; i <= n; i++) {
            // 动态规划转移方程：
            // dp[i] 表示到达第 i 级台阶的最小花费
            // 从第 i-1 级台阶或第 i-2 级台阶跳到第 i 级台阶
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

        // 返回到达楼顶的最小花费
        return dp[n];
    }
}

时间复杂度和空间复杂度都是 O(n)

滚动更新

注意到当 $i \geq 2$ 时， $dp[i]$ 只和 $dp[i-1]$ 与 $dp[i-2]$ 有关，因此可以使用滚动数组的思想，将空间复杂度优化到 $O(1)$ 。

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length; // 获取楼梯的阶数
        int prev = 0, curr = 0; // 初始化前两步的最小花费为0

        // 从第2步开始计算到达每一级台阶的最小花费
        for (int i = 2; i <= n; i++) {
            // 计算到达第i级台阶的最小花费
            int next = Math.min(curr + cost[i - 1], prev + cost[i - 2]);
            
            prev = curr; // 更新前一步的最小花费
            curr = next; // 更新当前步的最小花费
        }
        
        return curr; // 返回到达楼顶的最小花费
    }
}

• 时间复杂度： $O(n)$，其中 $n$ 是数组 cost 的长度。需要依次计算每个 dp 值，每个值的计算需要常数时间，因此总时间复杂度是 $O(n)$ 。
• 空间复杂度： $O(1)$。使用滚动数组的思想，只需要使用有限的额外空间。