Leetcode使用最小花费爬楼梯的解法思考与回溯
最近在做力扣动态规划(基础版)的50道题目，我觉得其中的的确确这么多题目都是非常有趣非常精彩同时也是非常深刻的，值得自己花时间好好琢磨。
自己最近在做打家劫舍和使用最小花费爬楼梯两道题目，我觉得这两道题目确实也是很不错的。尤其是打家劫舍这道题目，我想这应该是全世界的软件行业从业者应该都或多或少了解过的一道题目吧。
目录
一、最小花费爬楼梯题目与解答
二、自己提出的2个关键问题的解答
一、最小花费爬楼梯题目与解答
总之这是使用最小花费爬楼梯的题目，如图所示
这题的解答其实的确与打家劫舍问题类似，但是又不太一样。
class Solution { public: int minCostClimbingStairs(vector<int>& cost) { int n = cost.size(); vector<int> dp(n + 1); // dp[i] 表示到达第 i 个台阶的最小花费 dp[0] = 0; dp[1] = 0; // 从0或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个台阶）的最小花费 } };当然我还是始终认为如果我们只是追求写完这一题的主干就提交成功结束进入下一题我觉得首先得有2件事情得想明白：
1、这个如果是一整个完整的demo应该怎么做，完整形式又是什么？
2、动态规划的确好用，可以以一种非常高效的手法求出最优解最优值出来。只是，却并没有说明给出实现最优解的最优路径呢？这的确是令人感到非常遗憾的事情。
二、自己提出的2个关键问题的解答
现在我来对这2个问题逐一进行解答。
问题1、我来给出这个问题的完整demo
而且我在这里也做了与打家劫舍问题相关的比较
#include <iostream> #include <vector> #include <algorithm> // 包含min/max函数 using namespace std; // 最小花费爬楼梯核心解法 class Solution { public: int minCostClimbingStairs(vector<int>& cost) { int n = cost.size(); // dp[i]：到达第i个台阶的最小花费（i从0开始，顶部是第n个台阶） vector<int> dp(n + 1); dp[0] = 0; // 从第0个台阶开始，花费0 dp[1] = 0; // 从第1个台阶开始，花费0 // 状态转移：和打家劫舍类似，从i-1或i-2转移，取最小值 for (int i = 2; i <= n; ++i) { // 到i台阶：要么从i-1爬1步（加i-1台阶的花费），要么从i-2爬2步（加i-2台阶的花费） dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]); } return dp[n]; // 到达顶部（第n个台阶）的最小花费 } // 附带打家劫舍解法（方便对比） int rob(vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; if (n == 1) return nums[0]; vector<int> dp(n); dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]); for (int i = 2; i < n; ++i) { // 打家劫舍：要么不偷第i家（继承dp[i-1]），要么偷（dp[i-2]+nums[i]），取最大值 dp[i] = max(dp[i-1], dp[i-2] + nums[i]); } return dp.back(); } }; // 测试函数：打印测试用例和结果 void testMinCostClimbingStairs() { Solution sol; // 测试用例1：题目示例1 vector<int> cost1 = {10, 15, 20}; cout << "测试用例1：cost = [10,15,20]" << endl; cout << "最小花费：" << sol.minCostClimbingStairs(cost1) << endl; // 预期输出：15 // 测试用例2：题目示例2 vector<int> cost2 = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1}; cout << "\n测试用例2：cost = [1,100,1,1,1,100,1,1,100,1]" << endl; cout << "最小花费：" << sol.minCostClimbingStairs(cost2) << endl; // 预期输出：6 // 测试用例3：自定义（2个台阶） vector<int> cost3 = {5, 8}; cout << "\n测试用例3：cost = [5,8]" << endl; cout << "最小花费：" << sol.minCostClimbingStairs(cost3) << endl; // 预期输出：5（从第0个台阶开始，直接爬2步到顶部，花费5） // 测试用例4：自定义（5个台阶） vector<int> cost4 = {2, 3, 1, 4, 5}; cout << "\n测试用例4：cost = [2,3,1,4,5]" << endl; cout << "最小花费：" << sol.minCostClimbingStairs(cost4) << endl; // 预期输出：7（路径：0→2→4→顶部，花费2+1+4=7） } // 测试打家劫舍（可选） void testRob() { Solution sol; vector<int> nums = {1,2,3,1}; cout << "\n打家劫舍测试用例：nums = [1,2,3,1]" << endl; cout << "最大金额：" << sol.rob(nums) << endl; // 预期输出：4 } int main() { // 运行最小花费爬楼梯测试 testMinCostClimbingStairs(); // 可选：运行打家劫舍测试 // testRob(); return 0; }问题2、补充回溯路径的思考与解决方案，追溯最优解的路径
#include <iostream> #include <vector> #include <algorithm> #include <iterator> // 用于reverse打印路径 using namespace std; class Solution { public: // 核心：返回最小花费，并通过引用参数输出最优路径 int minCostClimbingStairs(vector<int>& cost, vector<int>& best_path) { int n = cost.size(); vector<int> dp(n + 1); // dp[i]：到达第i个台阶的最小花费 vector<int> path(n + 1); // path[i]：到达i台阶时，选择的是i-1(记1)还是i-2(记2) dp[0] = 0; dp[1] = 0; path[0] = -1; // 起点无来源 path[1] = -1; // 起点无来源 // 1. 动态规划 + 记录决策路径 for (int i = 2; i <= n; ++i) { int cost1 = dp[i-1] + cost[i-1]; // 从i-1爬上来的花费 int cost2 = dp[i-2] + cost[i-2]; // 从i-2爬上来的花费 if (cost1 < cost2) { dp[i] = cost1; path[i] = 1; // 选i-1 } else { dp[i] = cost2; path[i] = 2; // 选i-2 } } // 2. 回溯路径：从顶部(n)倒推回起点 best_path.clear(); int current = n; // 从顶部开始 while (current >= 2) { // 直到回到起点（0或1） if (path[current] == 1) { best_path.push_back(current - 1); // 记录选择的台阶（i-1） current -= 1; } else { best_path.push_back(current - 2); // 记录选择的台阶（i-2） current -= 2; } } // 补充起点（0或1） if (current == 1) { best_path.push_back(1); } else if (current == 0) { best_path.push_back(0); } // 反转路径，得到正序（从起点到顶部） reverse(best_path.begin(), best_path.end()); return dp[n]; } // 保留打家劫舍（方便对比） int rob(vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; if (n == 1) return nums[0]; vector<int> dp(n); dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]); for (int i = 2; i < n; ++i) { dp[i] = max(dp[i-1], dp[i-2] + nums[i]); } return dp.back(); } }; // 打印测试结果 + 最优路径 void testMinCostClimbingStairs() { Solution sol; vector<int> best_path; // 存储最优路径 // 测试用例1：题目示例1 vector<int> cost1 = {10, 15, 20}; cout << "===== 测试用例1 =====" << endl; cout << "输入cost：[10,15,20]" << endl; int min_cost1 = sol.minCostClimbingStairs(cost1, best_path); cout << "最小花费：" << min_cost1 << endl; cout << "最优路径（台阶索引）："; copy(best_path.begin(), best_path.end(), ostream_iterator<int>(cout, " → ")); cout << "顶部" << endl; // 补充顶部标识 cout << "路径解释：选择从第1个台阶（索引1）开始，爬1步到顶部，花费15" << endl << endl; // 测试用例2：题目示例2 vector<int> cost2 = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1}; cout << "===== 测试用例2 =====" << endl; cout << "输入cost：[1,100,1,1,1,100,1,1,100,1]" << endl; int min_cost2 = sol.minCostClimbingStairs(cost2, best_path); cout << "最小花费：" << min_cost2 << endl; cout << "最优路径（台阶索引）："; copy(best_path.begin(), best_path.end(), ostream_iterator<int>(cout, " → ")); cout << "顶部" << endl; cout << "路径解释：避开100的高花费台阶，走0→2→3→4→6→7→9→顶部，总花费1+1+1+1+1+1=6" << endl << endl; // 测试用例3：自定义（2个台阶） vector<int> cost3 = {5, 8}; cout << "===== 测试用例3 =====" << endl; cout << "输入cost：[5,8]" << endl; int min_cost3 = sol.minCostClimbingStairs(cost3, best_path); cout << "最小花费：" << min_cost3 << endl; cout << "最优路径（台阶索引）："; copy(best_path.begin(), best_path.end(), ostream_iterator<int>(cout, " → ")); cout << "顶部" << endl; cout << "路径解释：选第0个台阶开始，直接爬2步到顶部，花费5" << endl << endl; // 测试用例4：自定义（5个台阶） vector<int> cost4 = {2, 3, 1, 4, 5}; cout << "===== 测试用例4 =====" << endl; cout << "输入cost：[2,3,1,4,5]" << endl; int min_cost4 = sol.minCostClimbingStairs(cost4, best_path); cout << "最小花费：" << min_cost4 << endl; cout << "最优路径（台阶索引）："; copy(best_path.begin(), best_path.end(), ostream_iterator<int>(cout, " → ")); cout << "顶部" << endl; cout << "路径解释：0→2→4→顶部，花费2+1+4=7" << endl; } int main() { testMinCostClimbingStairs(); return 0; }这个问题的核心是path是开始记录是距离当前台阶的前面一个台阶还是前面两个台阶跳上来的，而best_path数组则是根据path进行回溯最优路径节点，然后进行翻转得到最优路径，二者是回溯能够成功实现的关键。当然这个代码的理解与复现并不轻松。