引言
在面对算法问题时，初学者常常会感到迷茫，不知道从何下手。尤其是像「爬楼梯最低花费」这样的动态规划问题，虽然看起来简单，但如果没有掌握合适的思维框架，往往难以快速找到解题的突破口。动态规划的核心思想是将问题分解为若干个子问题，通过递推的方式找到最优解，而理解这一点是解题的关键。
在这篇博客中，我将带你逐步构建出解决「爬楼梯最低花费」问题的完整动态规划思路。我们会从如何分析问题、构建状态到编写代码，全面展示解题的全过程，并通过优化后的代码，提升算法的效率。希望通过这一讲解，能够帮助你更好地理解动态规划的思维方式，让这类问题变得不再困难。
问题描述
给定一个整数数组 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 后一步一步跳到顶部，总花费为 6。
动态规划解题思路
我们可以将这个问题抽象为一个最优子结构问题，即：
- 要到达第
i个台阶，我们有两种选择：从第i-1个台阶或者从第i-2个台阶跳上来，选择这两者中花费较小的路径加上当前台阶的花费cost[i]。
因此，这里我们使用动态规划的思想来解决这个问题。动态规划的核心在于分解问题：当前的最优解是依赖于前面状态的最优解的。
1. 定义状态
我们可以定义一个数组 dp，其中 dp[i] 表示到达第 i 个台阶所需要的最低花费。我们的目标是找到 dp 数组的最优解。
首先我们明确以下几点：
- 可以从第 0 层或第 1 层开始，因此
dp[0] = cost[0]，dp[1] = cost[1]。 - 从第 2 层开始，我们需要从前面的两个台阶
i-1或i-2跳上来，因此状态转移方程是：
d p [ i ] = min ( d p [ i − 1 ] , d p [ i − 2 ] ) + c o s t [ i ] dp[i] = \min(dp[i-1], dp[i-2]) + cost[i] dp[i]=min(dp[i−1],dp[i−2])+cost[i]
这意味着到达第 i 个台阶，我们可以选择从 i-1 或 i-2 来，根据这两者中哪一个代价更小，再加上当前台阶的花费。
2. 初始条件
我们从第 0 层或第 1 层开始爬楼梯，所以 dp[0] 和 dp[1] 是已知的，分别等于 cost[0] 和 cost[1]。
3. 最终解
当我们到达楼梯的最后时，楼梯的顶部可以从倒数第二层或最后一层上去。因此，最终的最小花费就是：
result = min ( d p [ n − 1 ] , d p [ n − 2 ] ) \text{result} = \min(dp[n-1], dp[n-2]) result=min(dp[n−1],dp[n−2])
即：到达最后一个台阶或者倒数第二个台阶的最小花费。
动态规划代码实现
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n);
// 初始化第0层和第1层的最小花费
dp[0] = cost[0];
dp[1] = cost[1];
// 通过状态转移方程更新dp数组
for (int i = 2; i < n; ++i) {
dp[i] = min(dp[i-1], dp[i-2]) + cost[i];
}
// 返回到达楼梯顶部的最小花费
return min(dp[n-1], dp[n-2]);
}
int main() {
vector<int> cost1 = {10, 15, 20};
vector<int> cost2 = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
cout << "最低花费（示例1）: " << minCostClimbingStairs(cost1) << endl;
cout << "最低花费（示例2）: " << minCostClimbingStairs(cost2) << endl;
return 0;
}
代码讲解
- 我们首先定义了一个
dp数组，存储到达每个台阶的最小花费。 - 初始阶段，直接把
dp[0]和dp[1]初始化为cost[0]和cost[1]，因为这是最初的起点。 - 然后从第2层台阶开始，依次根据状态转移方程更新
dp数组的值。 - 最后，我们只需要返回
dp[n-1]和dp[n-2]的最小值，因为我们可以从这两层中的任意一层到达楼梯的顶部。
示例分析
示例 1:
输入：cost = [10, 15, 20]
dp[0] = 10dp[1] = 15- 计算
dp[2] = min(dp[1], dp[0]) + cost[2] = min(15, 10) + 20 = 30
结果为 min(dp[1], dp[2]) = min(15, 30) = 15，输出为 15。
示例 2:
输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
dp[0] = 1dp[1] = 100- 计算：
dp[2] = min(dp[1], dp[0]) + cost[2] = min(100, 1) + 1 = 2dp[3] = min(dp[2], dp[1]) + cost[3] = min(2, 100) + 1 = 3dp[4] = min(dp[3], dp[2]) + cost[4] = min(3, 2) + 1 = 3- 继续类似地计算到最后。
结果为 min(dp[9], dp[8]) = min(6, 104) = 6，输出为 6。
优化思路：减少空间复杂度
在上面的解法中，我们用了 dp 数组保存每一个台阶的最小花费，但是我们其实只需要保留前两个台阶的最小花费，因此可以将空间复杂度从 O(n) 降低到 O(1)。
优化后的代码如下：
int minCostClimbingStairsOptimized(vector<int>& cost) {
int n = cost.size();
int prev1 = cost[1], prev2 = cost[0];
for (int i = 2; i < n; ++i) {
int curr = min(prev1, prev2) + cost[i];
prev2 = prev1;
prev1 = curr;
}
return min(prev1, prev2);
}
总结
在这篇博客中，我们通过动态规划的思路，逐步构建了「爬楼梯最低花费」问题的解法。通过定义状态 dp[i] 表示到达第 i 个台阶的最小花费，我们可以依赖前两个台阶的最优解来求出当前台阶的最优解。最后通过状态转移公式，得到从底部爬到楼梯顶部的最小花费。