LeetCode 746 使用最小花费爬楼梯

当然可以！LeetCode 746 是一道经典的动态规划入门题，我来用 C++ 为你详细解释。

题目描述

给定一个整数数组 cost，其中每个元素 cost[i] 表示从第 i 个台阶向上爬需要支付的费用。一旦支付费用，你可以选择向上爬 1 步 或 2 步。
你可以从下标 0 或 1 的台阶开始爬。
目标：计算到达楼梯顶部（即最后一个台阶之后）的最小总花费。

核心思路

1. 动态规划定义：
   设 dp[i] 表示到达第 i 个台阶所需的最小总花费。
   最终答案：dp[n]，其中 n = cost.size()（即到达顶部的最小花费）。

2. 状态转移方程：
   到达第 i 个台阶的方式有两种：

   • 从第 i-1 个台阶爬一步，总花费为 dp[i-1] + cost[i-1]。
   • 从第 i-2 个台阶爬两步，总花费为 dp[i-2] + cost[i-2]。
     因此：

   dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
   

3. 初始条件：

   • dp[0] = 0：无需花费即可站在起点前。
   • dp[1] = 0：同理，可选择从下标 0 或 1 开始，无需初始花费。

C++ 代码实现

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        if (n == 0) return 0;
        
        vector<int> dp(n + 1, 0);  // dp[i] 表示到达第 i 个台阶的最小花费
        
        // 初始化：站在起点前（0 或 1）不需要花费
        dp[0] = 0;
        dp[1] = 0;
        
        // 动态规划计算
        for (int i = 2; i <= n; ++i) {
            dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
        }
        
        return dp[n];  // 到达顶部（第 n 个台阶）的最小花费
    }
};

优化空间复杂度

由于 dp[i] 只依赖于 dp[i-1] 和 dp[i-2]，可以用两个变量滚动优化：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        if (n == 0) return 0;
        
        int prev2 = 0;  // 对应 dp[i-2]
        int prev1 = 0;  // 对应 dp[i-1]
        
        for (int i = 2; i <= n; ++i) {
            int current = min(prev1 + cost[i-1], prev2 + cost[i-2]);
            prev2 = prev1;
            prev1 = current;
        }
        
        return prev1;  // 对应 dp[n]
    }
};

示例解释

输入：cost = [10, 15, 20]

• dp[0] = 0
• dp[1] = 0
• dp[2] = min(dp[1] + 15, dp[0] + 10) = min(0 + 15, 0 + 10) = 10
• dp[3] = min(dp[2] + 20, dp[1] + 15) = min(10 + 20, 0 + 15) = 15
  输出：15（从下标 1 开始，支付 15，直接跳两步到顶部）

关键点总结

1. 动态规划思想：用 dp 数组记录到达每个台阶的最小花费。
2. 状态转移：当前状态只依赖前两个状态，可用滚动数组优化空间。
3. 初始条件：起点前的位置无需花费。

这类问题是动态规划的基础，掌握后可轻松解决更复杂的路径优化问题！