题解 | 最小花费爬楼梯

1、解题思路

1. 动态规划： 定义 dp[i] 为到达第 i 个台阶的最低花费。初始条件：dp[0] = cost[0]，dp[1] = cost[1]。递推关系：dp[i] = cost[i] + min(dp[i-1], dp[i-2])。最终结果：min(dp[n-1], dp[n-2])，其中 n 是数组的长度。
2. 空间优化： 由于 dp[i] 只依赖于前两个状态，可以用两个变量代替整个 dp 数组，将空间复杂度优化到 O(1)。
3. 边界条件： 如果 cost 的长度为 1，直接返回 cost[0]。如果 cost 的长度为 2，返回 min(cost[0], cost[1])。

2、代码实现

C++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param cost int整型vector
     * @return int整型
     */
    int minCostClimbingStairs(vector<int>& cost) {
        // write code here
        int n = cost.size();
        if (n == 1) {
            return cost[0];
        }
        int a = cost[0], b = cost[1], c;
        for (int i = 2; i < n; ++i) {
            c = cost[i] + min(a, b);
            a = b;
            b = c;
        }
        return min(a, b);
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int minCostClimbingStairs (int[] cost) {
        // write code here
        int n = cost.length;
        if (n == 1) return cost[0];
        int a = cost[0], b = cost[1], c;
        for (int i = 2; i < n; ++i) {
            c = cost[i] + Math.min(a, b);
            a = b;
            b = c;
        }
        return Math.min(a, b);
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param cost int整型一维数组 
# @return int整型
#
class Solution:
    def minCostClimbingStairs(self , cost: List[int]) -> int:
        # write code here
        n = len(cost)
        if n == 1:
            return cost[0]
        a, b = cost[0], cost[1]
        for i in range(2, n):
            c = cost[i] + min(a, b)
            a, b = b, c
        return min(a, b)

3、复杂度分析

1. 初始条件： dp[0] = cost[0]，dp[1] = cost[1]。
2. 递推关系： 每次选择从 i-1 或 i-2 台阶上来的最小花费，加上当前台阶的花费。
3. 空间优化： 使用 a 和 b 代替 dp 数组，节省空间。
4. 最终结果： 到达顶部可以从 n-1 或 n-2 台阶上来，取两者的最小值。
5. 效率： 时间复杂度：O(n)，遍历一次数组。空间复杂度：O(1)，只使用常数空间。