1. 项目概述与核心价值最近在技术社区和求职圈里“华为OD机试”的热度一直居高不下尤其是C卷的题目常常成为大家讨论和准备的焦点。今天我想和大家深入聊聊C卷里一道非常经典的题目——“攀登者2”并且分享一个用C实现的完整思路与代码。这道题之所以值得拿出来单讲是因为它完美融合了数组处理、动态规划DP以及贪心算法的思想是检验一个程序员基础算法能力和逻辑思维深度的绝佳试金石。很多朋友在初次遇到时可能会被其看似复杂的场景描述所迷惑但一旦拆解清楚你会发现它的内核非常清晰。通过这道题你不仅能巩固DP的核心思想还能学会如何将实际问题抽象为可计算的模型这对于应对任何公司的算法面试都大有裨益。简单来说“攀登者2”题目描述了一个登山者面对一系列山丘用一个整数数组表示高度他需要规划一条路径使得总的“攀登难度”最低。这里的难度通常与相邻山丘的高度差相关。题目会给定具体的规则比如每次可以跨越1个或2个山丘目标是找到从起点到终点的最小代价路径。这本质上就是一个带有约束条件的最优化问题非常适合于用动态规划来求解。接下来我将从问题解析、思路形成、代码实现到调试技巧完整地走一遍希望能给正在准备机试或希望提升算法能力的你带来一些实实在在的参考。2. 问题深度解析与抽象建模拿到“攀登者2”的题目第一步不是急着写代码而是彻底读懂题目并将自然语言描述转化为精确的数学模型。这是解决所有算法问题的基石也是最容易出错的地方。2.1 题目场景与规则还原根据常见的题型描述我们可以将问题还原如下 假设有一个整数数组heights表示一系列山丘的高度。攀登者从第一个山丘下标0出发需要到达最后一个山丘下标n-1。他每次可以向前移动一步到达下一个山丘或两步跳过下一个山丘直接到达下下个山丘。每次移动他会产生一个“消耗”或“难度”这个值通常与前后两个山丘的高度差的绝对值相关。最常见的规定是消耗值等于高度差的绝对值。我们的目标是找到一条从起点到终点的移动路径使得路径上所有步骤的消耗总和最小。例如给定山丘高度数组为[1, 2, 3, 4, 5]。如果一步一步走路径为 1-2-3-4-5。消耗为 |2-1| |3-2| |4-3| |5-4| 1111 4。如果混合走例如 1-3跳一步消耗|3-1|2然后 3-4消耗1最后 4-5消耗1总消耗为 2114。另一种走法1-2消耗1然后 2-4跳一步消耗|4-2|2最后 4-5消耗1总消耗为 1214。 我们需要找出所有可能路径中的最小消耗。关键点抽象状态攀登者当前所在的山丘索引i。选择决策在状态i下攀登者可以做出的选择是移动到i1或者移动到i2前提是这些索引不越界。状态转移方程定义dp[i]为从山丘i出发到达终点n-1的最小消耗。那么在i点我们有两种选择选择跳到i1则后续的代价是dp[i1]加上从i到i1这一步的消耗cost(i, i1)。选择跳到i2则后续的代价是dp[i2]加上从i到i2这一步的消耗cost(i, i2)。dp[i]应该等于这两种选择中代价较小的那个。 因此状态转移方程为dp[i] min(dp[i1] cost(i, i1), dp[i2] cost(i, i2))其中cost(a, b) abs(heights[b] - heights[a])。边界条件Base Case当i n-1时已经到达终点无需移动所以dp[n-1] 0。当i n-2时只剩最后一个山丘只能移动到n-1所以dp[n-2] cost(n-2, n-1)。注意这里不能跳两步因为i2会越界。2.2 为什么选择动态规划这是一个典型的多阶段决策最优化问题并且具有“最优子结构”和“无后效性”这两个DP问题的核心特征。最优子结构从i点到终点的最优路径必然包含了从i1或i2到终点的最优路径。如果从i到终点的最优路径是经过i1的那么这条路径从i1到终点的部分也必然是从i1到终点的最优路径否则我们可以替换成更优的从而得到从i出发更优的路径产生矛盾。无后效性未来从i1或i2到终点的最优解只依赖于当前的状态i和所做的决策而不依赖于过去是如何到达状态i的。dp[i]的值一旦确定就不会改变。基于以上两点我们可以用DP表格数组来存储子问题的解避免重复计算这正是动态规划高效的原因。与之相对的如果使用深度优先搜索DFS暴力枚举所有路径时间复杂度将达到 O(2^n)在n较大时完全不可接受。DP可以将时间复杂度降低到 O(n)。3. C实现详解与逐行代码分析理清了思路接下来就是将其转化为可靠的C代码。我将提供一个清晰、健壮且带有详细注释的实现。3.1 核心函数实现#include iostream #include vector #include cmath // 用于 abs 函数 #include algorithm // 用于 min 函数 #include climits // 用于 INT_MAX using namespace std; /** * 计算攀登者从起点到终点的最小消耗。 * param heights 表示山丘高度的整数数组。 * return 最小消耗值。 */ int minClimbingCost(const vectorint heights) { int n heights.size(); if (n 1) { // 如果只有一个或没有山丘无需移动消耗为0 return 0; } // 1. 定义DP数组。dp[i] 表示从山丘 i 到达终点 (n-1) 的最小消耗。 vectorint dp(n, 0); // 2. 初始化边界条件从后往前填表 // 终点dp[n-1] 0 (已经初始化) // 倒数第二个点只能走到终点 dp[n-1] 0; // 注意这里需要先计算 dp[n-2]因为转移方程可能用到 dp[n-1] 和 dp[n]越界。 // 更安全的做法是从 n-2 开始倒序计算。 // 我们重新规划循环显式处理边界。 // 3. 倒序计算DP数组从 n-2 到 0 for (int i n-2; i 0; --i) { // 选择1移动到 i1 int costOneStep abs(heights[i1] - heights[i]); int totalCostOneStep costOneStep (i1 n ? dp[i1] : 0); // 防御性检查此处i1肯定有效 // 选择2移动到 i2 (如果存在) int totalCostTwoSteps INT_MAX; // 初始化为最大值表示不可达 if (i 2 n) { int costTwoSteps abs(heights[i2] - heights[i]); totalCostTwoSteps costTwoSteps dp[i2]; } // 决策取两种选择中代价较小的 dp[i] min(totalCostOneStep, totalCostTwoSteps); } // 4. 最终结果存储在 dp[0]即从起点(0)到终点的最小消耗 return dp[0]; }3.2 代码关键点剖析与注意事项DP数组的定义与方向我们定义了dp[i]为从i到终点的最小消耗。这是一种“后向DP”思考方式是“从当前位置出发后续最少要花多少代价才能到终点”。这比定义“从起点到i的最小消耗”前向DP在某些情况下更直观因为终点状态是确定的消耗为0。为什么倒序计算因为状态转移方程dp[i]依赖于dp[i1]和dp[i2]。我们必须先知道后面子问题的解才能计算前面的。所以循环从n-2开始递减到0。边界条件的处理n 1的情况需要单独处理避免数组访问越界。在计算totalCostTwoSteps时必须检查i2 n是否成立。如果不成立则这种选择无效。我们将其代价初始化为INT_MAX这样在min比较时就不会被选中。虽然在这个循环里i1永远小于n因为i最大为n-2但保持防御性编程的习惯是好的所以加了(i1 n ? dp[i1] : 0)的判断。消耗函数的计算abs(heights[b] - heights[a])使用了cmath中的abs函数它对于整数参数是重载的。也可以使用cstdlib中的abs。确保包含正确的头文件。空间复杂度优化可选观察状态转移方程dp[i]只依赖于dp[i1]和dp[i2]。这意味着我们不需要存储整个dp数组只需要维护两个变量记录“后一步”和“后两步”的结果即可。这可以将空间复杂度从 O(n) 降低到 O(1)。但对于机试而言O(n) 的空间通常完全可接受代码清晰易读更重要。优化后的版本如下供学有余力者参考int minClimbingCostOptimized(const vectorint heights) { int n heights.size(); if (n 1) return 0; if (n 2) return abs(heights[1] - heights[0]); // 初始化“后两步”和“后一步”的dp值 int dp_i_plus_2 0; // dp[n-1] 0 int dp_i_plus_1 abs(heights[n-1] - heights[n-2]); // dp[n-2] int dp_current 0; // 从 n-3 开始倒推 for (int i n-3; i 0; --i) { int costOneStep abs(heights[i1] - heights[i]) dp_i_plus_1; int costTwoSteps abs(heights[i2] - heights[i]) dp_i_plus_2; dp_current min(costOneStep, costTwoSteps); // 滚动更新变量为下一次迭代做准备 dp_i_plus_2 dp_i_plus_1; dp_i_plus_1 dp_current; } // 循环结束时dp_i_plus_1 存储的就是 dp[0] return dp_i_plus_1; }4. 完整测试用例与调试流程写出代码只是第一步用全面的测试用例验证其正确性至关重要。以下是我设计的一组测试用例覆盖了各种边界和典型情况。// 辅助测试函数 void testMinClimbingCost() { cout 开始测试 minClimbingCost endl; // 测试用例1题目示例或简单递增 vectorint heights1 {1, 2, 3, 4, 5}; int result1 minClimbingCost(heights1); cout 测试1 [1,2,3,4,5]: 预期最小消耗为4实际结果为: result1 (result1 4 ? (通过) : (失败)) endl; // 测试用例2高度有起伏测试决策 vectorint heights2 {10, 15, 20, 10, 25}; // 手动计算一条路径10-20 (|20-10|10), 20-10 (10), 10-25 (15) 总35 // 更优路径10-15 (5), 15-10 (5), 10-25 (15) 总25 // 或者10-20 (10), 20-25 (5) 总15 (最优) int result2 minClimbingCost(heights2); cout 测试2 [10,15,20,10,25]: 预期最小消耗为15实际结果为: result2 (result2 15 ? (通过) : (失败)) endl; // 测试用例3两个山丘 vectorint heights3 {100, 50}; int result3 minClimbingCost(heights3); cout 测试3 [100,50]: 预期最小消耗为50实际结果为: result3 (result3 50 ? (通过) : (失败)) endl; // 测试用例4只有一个山丘起点即终点 vectorint heights4 {42}; int result4 minClimbingCost(heights4); cout 测试4 [42]: 预期最小消耗为0实际结果为: result4 (result4 0 ? (通过) : (失败)) endl; // 测试用例5空数组虽然题目可能不会给但防御性编程 vectorint heights5 {}; int result5 minClimbingCost(heights5); cout 测试5 []: 预期最小消耗为0实际结果为: result5 (result5 0 ? (通过) : (失败)) endl; // 测试用例6高度全部相同消耗应为0 vectorint heights6 {7, 7, 7, 7, 7}; int result6 minClimbingCost(heights6); cout 测试6 [7,7,7,7,7]: 预期最小消耗为0实际结果为: result6 (result6 0 ? (通过) : (失败)) endl; // 测试用例7下山比上山消耗大注意消耗是绝对值所以一样。 vectorint heights7 {5, 1, 5, 1, 5}; // 路径5-5 (0), 5-1 (4), 1-5 (4) 总8 // 另一条5-1 (4), 1-1 (0), 1-5 (4) 总8 // 最优可能是跳着走5-5 (0), 5-1 (4), 1-5 (4) 还是8。似乎都是8。 int result7 minClimbingCost(heights7); cout 测试7 [5,1,5,1,5]: 预期最小消耗为8实际结果为: result7 (result7 8 ? (通过) : (失败)) endl; cout 测试结束 endl; } int main() { testMinClimbingCost(); return 0; }运行这段测试代码你应该能看到所有测试用例都通过。在机试环境中务必自己先构思几个简单的测试用例在脑海里或纸上演算一下预期结果然后再运行程序对比。这是快速发现逻辑错误的最有效方法。注意机试平台可能使用不同的函数签名比如输入是int* heights, int length。务必仔细阅读题目给出的输入输出格式说明。上述实现基于vectorint如果平台是C风格数组稍作修改即可。5. 常见陷阱、调试技巧与性能分析即使思路正确实现时也可能掉进一些坑里。下面是我在练习和教学中总结的几个常见问题。5.1 易错点排查清单数组下标越界这是最经典的错误。在访问heights[i1]和heights[i2]以及dp[i1]和dp[i2]时必须确保索引i1和i2小于数组长度n。我们的代码通过在计算两步跳时增加if (i2 n)判断来避免。DP数组初始化错误dp[n-1]必须初始化为0因为已经在终点没有消耗。如果错误地初始化为一个很大的数或者INT_MAX会导致后续计算全部出错。循环方向错误由于dp[i]依赖于后面的状态必须从后往前计算。如果写成从前往后在计算dp[i]时dp[i1]和dp[i2]还没有被正确计算出来除非你换一种DP定义方式。状态转移方程遗漏情况只考虑了跳一步忘了可以跳两步或者反之。必须完整考虑题目允许的所有决策。消耗计算错误误以为消耗是高度差而不是高度差的绝对值。仔细读题确认消耗的计算公式。有时题目可能会是高度差的平方或其他函数。输入处理错误机试时需要自己编写输入读取代码。常见的输入格式是第一行一个整数n第二行n个整数代表高度。务必正确处理。// 标准的输入处理示例 int main() { int n; cin n; vectorint heights(n); for (int i 0; i n; i) { cin heights[i]; } int result minClimbingCost(heights); cout result endl; return 0; }5.2 调试技巧如何快速定位问题当程序输出与预期不符时打印DP表在函数内部计算完整个dp数组后将其打印出来。对于小规模测试用例手动演算一遍dp值与程序输出对比不一致的地方就是错误点。// ... 计算dp之后 ... cout DP array: ; for (int val : dp) cout val ; cout endl;使用IDE调试器如果环境允许如本地VS Code Dev C等设置断点单步执行观察变量i,costOneStep,totalCostOneStep,totalCostTwoSteps,dp[i]的变化看哪一步计算与预期不符。构造最小反例如果测试用例复杂尝试构造一个最简单的、能暴露问题的例子。比如n3或n4的情况手工计算一遍再与程序输出对比。5.3 时间与空间复杂度分析时间复杂度我们有一个从n-2到0的单层循环循环内是常数时间的操作计算绝对值、比较、加法。因此总时间复杂度为O(n)其中n是山丘的数量。这完全满足机试的性能要求通常n在 10^5 以内。空间复杂度使用了一个长度为n的dp数组因此空间复杂度为O(n)。如果采用滚动变量优化可以降至O(1)。在华为OD或其他公司的机试中明确写出复杂度分析有时是加分项它展示了你的代码评估能力。6. 举一反三题型变种与扩展思考“攀登者2”是一个模型掌握它之后可以解决一系列类似问题。这里列举几个可能的变种你可以尝试独立实现巩固理解。6.1 变种一攀登者1每次最多跳k步这是更一般化的情况。题目可能变为每次可以跳1到k步k是一个给定的常数比如3或5。求最小消耗。思路调整状态转移方程需要遍历所有可能的跳跃步数j(从1到k且ij n)。dp[i] min( dp[ij] cost(i, ij) )其中j从1遍历到k。 初始化dp[n-1] 0。计算时仍需从后往前。6.2 变种二消耗规则变化消耗可能不是简单的绝对值差。例如消耗为高度差的平方cost(a, b) (heights[b] - heights[a]) * (heights[b] - heights[a])。如果是从低处往高处爬heights[b] heights[a]消耗为高度差如果是从高处往低处走消耗为0或一个固定值。思路调整只需修改cost函数的计算方式DP框架完全不变。这体现了将“问题建模”与“求解算法”分离的好处。6.3 变种三输出具体路径题目不仅要求最小消耗值还要求输出一条具体的路径即经过的山丘下标序列。思路调整在DP过程中除了记录最小消耗值dp[i]还需要一个path[i]数组记录在状态i做出最优选择时下一步跳到了哪个索引。在状态转移时当发现dp[i1] cost(...)更优就记录path[i] i1如果dp[i2] cost(...)更优就记录path[i] i2。计算结束后从i0开始根据path[i]依次输出直到到达终点n-1。vectorint getPath(const vectorint heights, const vectorint path) { vectorint result; int i 0; result.push_back(i); while (i ! heights.size() - 1) { i path[i]; result.push_back(i); } return result; } // 在DP循环中更新path if (totalCostOneStep totalCostTwoSteps) { // 注意等号处理决定优先级 dp[i] totalCostOneStep; path[i] i 1; } else { dp[i] totalCostTwoSteps; path[i] i 2; }6.4 从“攀登者”到其他DP问题这个问题的本质是“带权值的最短路径”问题在一个一维线性序列上的特例。它的思想可以迁移到许多场景青蛙跳台阶问题每次跳1或2级求跳到第n级的方法数。状态转移方程为f(n) f(n-1) f(n-2)。使用最小花费爬楼梯cost[i]表示第i级楼梯的体力值每次可以爬1或2级求爬到顶部的最小体力消耗。这与“攀登者”几乎一模一样。股票买卖系列问题简单版虽然场景不同但那种“当前状态取决于前一个或前两个状态”的DP思想是相通的。理解一个问题的本质比死记硬背十道题的答案要有用得多。在准备机试时建议对每一道做过的题都进行这种“抽象-扩展”的思考。7. 机试实战策略与时间管理最后结合华为OD机试的环境分享几点实战心得。审题至少三分钟不要一上来就敲代码。仔细阅读题目描述用笔在纸上画出样例确保完全理解输入、输出格式以及所有规则。误解题意是导致提交失败的最主要原因。先写思路注释在代码编辑区先写下解题思路的关键步骤比如DP的定义、状态转移方程、边界条件。这能帮助你理清逻辑也方便在检查时快速回顾。实现核心函数像本文这样先实现一个清晰、正确的核心函数如minClimbingCost。确保它通过你手头的小样例。完善输入输出根据题目要求的格式补全main函数中的输入读取和结果输出。特别注意机试平台可能使用文件输入输出或标准输入输出仔细看说明。输出通常不需要任何额外格式如“结果是”直接输出答案数字或字符串。测试与调试使用题目给的样例进行测试。自己设计2-3个边界用例如n1, n2 全部相等 极端高度差进行测试。如果平台有“自测”功能充分利用。如果没有就在本地编译器或在线IDE上测试。时间分配通常机试有多道题。如果一道题卡住超过20分钟还没有清晰思路可以先做标记跳过去做其他题。所有题目都有基础分确保拿到能拿的分比死磕一道题更重要。代码风格虽然不占分但清晰的代码结构、有意义的变量名、适当的注释能让你在检查时更轻松减少低级错误。“攀登者2”这类题目一旦掌握其DP内核代码实现是非常快速的。平时多练习这类经典模型在考场上就能迅速识别并套用为解决更复杂的问题节省宝贵时间。希望这篇长文能帮你彻底吃透这道题在未来的机试中游刃有余。