最近在做力扣动态规划(基础版)的50道题目我觉得其中的的确确这么多题目都是非常有趣非常精彩同时也是非常深刻的值得自己花时间好好琢磨。自己最近在做打家劫舍和使用最小花费爬楼梯两道题目我觉得这两道题目确实也是很不错的。尤其是打家劫舍这道题目我想这应该是全世界的软件行业从业者应该都或多或少了解过的一道题目吧。目录一、最小花费爬楼梯题目与解答二、自己提出的2个关键问题的解答一、最小花费爬楼梯题目与解答总之这是使用最小花费爬楼梯的题目如图所示这题的解答其实的确与打家劫舍问题类似但是又不太一样。class Solution { public: int minCostClimbingStairs(vectorint cost) { int n cost.size(); vectorint 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(vectorint cost) { int n cost.size(); // dp[i]到达第i个台阶的最小花费i从0开始顶部是第n个台阶 vectorint 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(vectorint nums) { int n nums.size(); if (n 0) return 0; if (n 1) return nums[0]; vectorint 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 vectorint cost1 {10, 15, 20}; cout 测试用例1cost [10,15,20] endl; cout 最小花费 sol.minCostClimbingStairs(cost1) endl; // 预期输出15 // 测试用例2题目示例2 vectorint cost2 {1, 100, 1, 1, 1, 100, 1, 1, 100, 1}; cout \n测试用例2cost [1,100,1,1,1,100,1,1,100,1] endl; cout 最小花费 sol.minCostClimbingStairs(cost2) endl; // 预期输出6 // 测试用例3自定义2个台阶 vectorint cost3 {5, 8}; cout \n测试用例3cost [5,8] endl; cout 最小花费 sol.minCostClimbingStairs(cost3) endl; // 预期输出5从第0个台阶开始直接爬2步到顶部花费5 // 测试用例4自定义5个台阶 vectorint cost4 {2, 3, 1, 4, 5}; cout \n测试用例4cost [2,3,1,4,5] endl; cout 最小花费 sol.minCostClimbingStairs(cost4) endl; // 预期输出7路径0→2→4→顶部花费2147 } // 测试打家劫舍可选 void testRob() { Solution sol; vectorint 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(vectorint cost, vectorint best_path) { int n cost.size(); vectorint dp(n 1); // dp[i]到达第i个台阶的最小花费 vectorint 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(vectorint nums) { int n nums.size(); if (n 0) return 0; if (n 1) return nums[0]; vectorint 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; vectorint best_path; // 存储最优路径 // 测试用例1题目示例1 vectorint 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_iteratorint(cout, → )); cout 顶部 endl; // 补充顶部标识 cout 路径解释选择从第1个台阶索引1开始爬1步到顶部花费15 endl endl; // 测试用例2题目示例2 vectorint 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_iteratorint(cout, → )); cout 顶部 endl; cout 路径解释避开100的高花费台阶走0→2→3→4→6→7→9→顶部总花费1111116 endl endl; // 测试用例3自定义2个台阶 vectorint 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_iteratorint(cout, → )); cout 顶部 endl; cout 路径解释选第0个台阶开始直接爬2步到顶部花费5 endl endl; // 测试用例4自定义5个台阶 vectorint 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_iteratorint(cout, → )); cout 顶部 endl; cout 路径解释0→2→4→顶部花费2147 endl; } int main() { testMinCostClimbingStairs(); return 0; }这个问题的核心是path是开始记录是距离当前台阶的前面一个台阶还是前面两个台阶跳上来的而best_path数组则是根据path进行回溯最优路径节点然后进行翻转得到最优路径二者是回溯能够成功实现的关键。当然这个代码的理解与复现并不轻松。