1. 项目概述从“猴子爬山”到算法思维最近在整理一些经典的编程练习题发现“猴子爬山”这道题在各大公司的机试和面试中出现的频率相当高尤其是像华为OD这样的招聘环节。这道题本身并不复杂但它是一个绝佳的载体能同时考察候选人的问题抽象能力、动态规划思维以及多语言编码基本功。很多朋友在初次接触时可能会被它看似“幼稚”的题目描述迷惑觉得不就是一只猴子爬楼梯吗但真正动手实现尤其是要写出高效、优雅的代码时才会发现里面有不少门道。简单来说“猴子爬山”问题描述通常是一只猴子要爬一个有N级台阶的山它一次可以爬1级、2级或3级台阶。问这只猴子爬到山顶第N级总共有多少种不同的爬法。这本质上就是一个计算路径总数的问题是动态规划Dynamic Programming, DP入门最经典的例题之一。它之所以备受青睐是因为它完美地映射了动态规划的核心思想将大问题分解为重叠的子问题并存储子问题的解以避免重复计算。今天我就结合自己带新人以及面试别人的经验把这道题的解题思路、核心算法、代码实现以及不同语言下的编码细节彻底讲透。我会提供Java、C和Python三种主流语言的实现代码并重点分析每种语言在解决此类问题时的性能考量、易错点以及代码风格。无论你是正在准备华为机试还是想巩固动态规划基础或者单纯想看看不同语言的实现差异这篇文章都能给你带来直接的帮助。2. 核心思路拆解为什么是动态规划在动手写代码之前我们必须把思路理清楚。很多初学者一看到“多少种方法”可能会下意识地想用递归去枚举所有可能性。这当然是一种方法但效率是灾难性的。我们来分析一下。2.1 从递归到动态规划的思维跃迁假设我们定义函数f(n)表示爬到第n级台阶的方法总数。根据题目猴子最后一步可能从第n-1级跨1步上来也可能从第n-2级跨2步上来或者从第n-3级跨3步上来。由于最后一步是独立的那么爬到第n级的总方法数就等于到达前面这三个“前置状态”的方法数之和。于是我们得到了这个问题的状态转移方程f(n) f(n-1) f(n-2) f(n-3)同时我们需要边界条件Base Casef(1) 1只有一种方法爬1级f(2) 2两种方法11 或直接爬2级f(3) 4四种方法111, 12, 21, 3如果直接用递归实现这个方程代码会非常简洁但计算f(30)可能就需要等上好几秒计算f(50)基本就别想了。为什么呢因为递归树展开了大量的重复计算。例如计算f(5)f(5) f(4) f(3) f(2)计算f(4)时又要计算f(3)和f(2)。这里的f(3)和f(2)就被重复计算了。随着n增大这种重复是指数级增长的。实操心得在机试或面试中如果你只给出递归解法面试官大概率会追问“这个解法的时间复杂度是多少当N很大时比如1000会怎么样” 这时你再引出动态规划进行优化就能很好地展示你的思维层次。如果直接给出DP解法则显得你基础扎实准备充分。2.2 动态规划方案的确定动态规划的核心就是用一张表通常是数组把子问题的解存起来空间换时间。对于本题我们有两种主流的DP实现方式自顶向下的记忆化搜索Memoization在递归的基础上加一个缓存数组计算过的f(n)就存起来下次直接用。这本质还是递归思想但避免了重复计算。自底向上的迭代法Tabulation从小问题开始一步步递推到大问题。这是我们最常用、也最推荐在机试中使用的方法因为它通常具有更好的空间优化潜力和更直观的代码结构。我们选择自底向上的迭代法。具体思路是创建一个数组dp其中dp[i]表示爬到第i级台阶的方法数。初始化dp[1],dp[2],dp[3]。然后从i 4开始循环到n利用公式dp[i] dp[i-1] dp[i-2] dp[i-3]依次计算每个dp[i]。最终dp[n]就是答案。这个算法的时间复杂度是O(N)只需要一次遍历空间复杂度如果存储整个数组也是O(N)。但我们可以进一步优化因为计算dp[i]只依赖于前三个状态所以我们可以只用三个变量滚动更新将空间复杂度降到O(1)。这在机试中是一个很好的加分点。3. 多语言代码实现与细节解析接下来我们分别用Java、C和Python实现上述的自底向上迭代DP算法并会给出空间优化后的版本。我会详细注释关键行并指出各语言实现中需要特别注意的地方。3.1 Java实现严谨与健壮性Java版本的特点是类型明确、代码结构清晰非常适合展示算法逻辑。我们首先实现基础版。import java.util.Scanner; public class MonkeyClimb { /** * 基础动态规划方法 * param n 台阶总数 * return 爬到第n级台阶的不同方法数 */ public static long climbWaysBasic(int n) { if (n 0) return 0; // 处理边界情况 if (n 1) return 1; if (n 2) return 2; if (n 3) return 4; // dp数组long类型防止大数溢出 long[] dp new long[n 1]; dp[1] 1; dp[2] 2; dp[3] 4; for (int i 4; i n; i) { // 状态转移方程 dp[i] dp[i - 1] dp[i - 2] dp[i - 3]; } return dp[n]; } /** * 空间优化版动态规划滚动数组 * 只维护三个变量空间复杂度O(1) * param n 台阶总数 * return 爬到第n级台阶的不同方法数 */ public static long climbWaysOptimized(int n) { if (n 0) return 0; if (n 1) return 1; if (n 2) return 2; if (n 3) return 4; // 初始化前三个状态 long a 1; // 代表 dp[i-3] long b 2; // 代表 dp[i-2] long c 4; // 代表 dp[i-1] long result 0; for (int i 4; i n; i) { // 计算当前状态 result a b c; // 滚动更新状态变量 a b; b c; c result; } return result; } public static void main(String[] args) { Scanner scanner new Scanner(System.in); System.out.print(请输入台阶数 n: ); int n scanner.nextInt(); scanner.close(); // 测试两种方法 long ways1 climbWaysBasic(n); long ways2 climbWaysOptimized(n); System.out.println(基础DP方法结果: ways1); System.out.println(优化DP方法结果: ways2); } }Java实现要点解析数据类型选择方法数可能增长得非常快类似三阶斐波那契数列。当n较大时int类型很容易溢出。因此这里使用了long类型。在极端情况下如n100甚至可能需要使用BigInteger。边界处理这是机试中极易失分的地方。必须对n 0,n 1, 2, 3的情况进行单独判断和处理否则在创建数组或访问数组时会抛出ArrayIndexOutOfBoundsException。空间优化climbWaysOptimized方法展示了经典的“滚动数组”思想。我们只关心前三个状态所以用三个变量a, b, c不断滚动更新完全不需要一个长度为n的数组。这在处理大规模数据时非常有用。输入输出使用了Scanner进行控制台输入这是华为机试OJ环境中的常见做法。记得在使用后关闭scanner。3.2 C实现效率与控制力C版本追求更高的运行效率和更精细的内存控制代码风格上更贴近底层。#include iostream #include vector using namespace std; /** * 基础动态规划方法 * param n 台阶总数 * return 爬到第n级台阶的不同方法数 */ long long climbWaysBasic(int n) { if (n 0) return 0; if (n 1) return 1; if (n 2) return 2; if (n 3) return 4; // 使用vector容器避免手动管理内存 vectorlong long dp(n 1, 0); dp[1] 1; dp[2] 2; dp[3] 4; for (int i 4; i n; i) { dp[i] dp[i - 1] dp[i - 2] dp[i - 3]; } return dp[n]; } /** * 空间优化版动态规划 * param n 台阶总数 * return 爬到第n级台阶的不同方法数 */ long long climbWaysOptimized(int n) { if (n 0) return 0; if (n 1) return 1; if (n 2) return 2; if (n 3) return 4; long long a 1; // dp[i-3] long long b 2; // dp[i-2] long long c 4; // dp[i-1] long long result 0; for (int i 4; i n; i) { result a b c; a b; b c; c result; } return result; } int main() { int n; cout 请输入台阶数 n: ; cin n; long long ways1 climbWaysBasic(n); long long ways2 climbWaysOptimized(n); cout 基础DP方法结果: ways1 endl; cout 优化DP方法结果: ways2 endl; return 0; }C实现要点解析数据类型同样使用long long来应对可能的大数。在C中long的长度可能和int一样在Windows 64位LLP64模型下所以明确使用long long更保险。容器选择这里使用了std::vector而非原生数组。vector会自动管理内存更安全便捷是现代C中的首选。如果为了极致性能且n固定也可以使用new分配数组但务必记得delete[]。前增运算符在循环for (int i 4; i n; i)中习惯使用前置递增i。对于内置类型它与i性能无差异但养成使用i的习惯在遇到重载了运算符的迭代器对象时会有性能优势。输入输出使用cin和cout注意它们比C的scanf/printf慢但在数据量不大的机试题中完全够用且更类型安全。3.3 Python实现简洁与高效Python版本以其无与伦比的代码简洁性著称非常适合快速实现算法原型和解题。def climb_ways_basic(n: int) - int: 基础动态规划方法 :param n: 台阶总数 :return: 爬到第n级台阶的不同方法数 if n 0: return 0 if n 1: return 1 if n 2: return 2 if n 3: return 4 # 初始化dp列表 dp [0] * (n 1) dp[1], dp[2], dp[3] 1, 2, 4 for i in range(4, n 1): dp[i] dp[i - 1] dp[i - 2] dp[i - 3] return dp[n] def climb_ways_optimized(n: int) - int: 空间优化版动态规划 :param n: 台阶总数 :return: 爬到第n级台阶的不同方法数 if n 0: return 0 if n 1: return 1 if n 2: return 2 if n 3: return 4 a, b, c 1, 2, 4 # 分别代表 dp[i-3], dp[i-2], dp[i-1] for _ in range(4, n 1): # 并行赋值实现状态的滚动更新 a, b, c b, c, a b c return c if __name__ __main__: try: n int(input(请输入台阶数 n: )) result_basic climb_ways_basic(n) result_opt climb_ways_optimized(n) print(f基础DP方法结果: {result_basic}) print(f优化DP方法结果: {result_opt}) except ValueError: print(输入错误请输入一个整数。)Python实现要点解析类型注解函数定义中的- int是类型注解Python 3.5它不强制类型检查但能极大地提高代码的可读性和可维护性是良好的编程习惯。列表初始化dp [0] * (n 1)是快速创建初始化列表的惯用法。注意如果列表元素是可变对象如列表这种方法会有浅拷贝问题但这里元素是整数所以安全。并行赋值在优化版函数中a, b, c b, c, a b c这行代码是精髓。它在一行内同时完成了计算新值和状态滚动既简洁又高效避免了使用临时变量。这是Python独有的语法糖。大整数支持Python的整数 (int) 是任意精度的这意味着你基本不用担心整数溢出问题。当n很大时Python会自动处理大数运算而Java和C则需要特殊类型 (BigInteger, 可能需要__int128或第三方库)。错误处理使用try-except捕获输入非整数的情况使程序更健壮。在机试OJ中输入通常是规整的但自己测试时很有用。4. 性能对比与语言特性深度探讨实现完了我们来深入聊聊不同语言选择背后的考量。这不仅是解一道题更是理解不同工具的特长。4.1 时间复杂度与空间复杂度三种语言实现的算法核心逻辑一致因此时间和空间复杂度在理论上是相同的基础DP时间复杂度 O(N)空间复杂度 O(N)。优化DP时间复杂度 O(N)空间复杂度 O(1)。但在实际运行时由于语言本身的开销如Python的解释执行、Java的JVM启动绝对耗时会是 C Java Python。对于机试只要算法复杂度正确通常都能在规定时间内通过。关键在于你是否能写出空间复杂度为 O(1) 的优化版本这直接体现了你对算法优化的理解深度。4.2 各语言在机试中的实战技巧Java优势生态成熟API丰富面向对象思想体现得好。在需要复杂数据结构和算法如图论时Collections框架能节省大量时间。注意点输入输出华为OJ通常使用Scanner但对于大数据量输入BufferedReader会快得多。可以准备一个快速IO的模板。数组越界这是最常见的运行时错误。务必仔细处理边界条件。默认包机试环境通常要求类名为Main且不要有package语句。C优势运行速度最快对内存和底层控制力强。STL标准模板库提供了强大且高效的容器和算法。注意点头文件记住常用头文件如iostream,vector,algorithm,queue等。using namespace std;在竞赛或机试中为了编码速度可以写但在大型工程中不建议。内存与指针如果用到动态内存千万注意配对new/delete防止内存泄漏。优先使用vector,string等RAII容器。Python优势代码极其简洁开发速度快。内置的列表、字典、集合等数据结构用起来行云流水。强大的切片、列表推导式等语法能让代码短小精悍。注意点性能陷阱Python的循环较慢。如果遇到数据规模极大的题目如N10^6纯Python循环可能超时。此时可以考虑使用NumPy如果环境允许或思考更数学化的解法。递归深度默认递归深度限制约1000层。如果题目需要深度递归如树的后序遍历需要sys.setrecursionlimit()来调整。空格与缩进语法强制缩进复制代码时容易出错需格外小心。实操心得在真正的华为OD机试中通常可以自选编程语言。我的建议是选择你最熟悉、编码速度最快的那一门。熟练度远胜于语言的微小优势。如果你三样都还行那么对于纯算法题Python的快速实现能帮你节省大量时间用于思考和检查对于涉及复杂系统建模或性能要求极高的题C可能更合适Java则是一个稳健的折中选择。5. 问题扩展与举一反三“猴子爬山”是一个很好的起点但面试官往往不会止步于此。他们会通过变化问题来考察你的思维灵活度。这里我列举几个常见的变体你可以自己先思考再看解析。5.1 变体一步长变化题目如果猴子一次能爬的台阶数不是一个固定的集合{1,2,3}而是一个通过参数传入的数组steps[]例如steps [1, 3, 5]该如何求解解析 这变成了一个完全背包问题的变种。台阶总数N是背包容量每一步的步长是物品的重量且每种步长可以无限次使用——完全背包求装满背包的“排列数”因为顺序不同爬法不同。 状态转移方程变为dp[i] sum(dp[i - step])其中step遍历steps数组且i step。 初始化dp[0] 1爬到第0级台阶有一种方法不动。def climb_ways_variable_steps(n, steps): if n 0: return 0 dp [0] * (n 1) dp[0] 1 # 关键初始化 steps.sort() # 排序可选便于逻辑清晰 for i in range(1, n 1): for step in steps: if i step: dp[i] dp[i - step] return dp[n] # 示例一次可以爬1、3、5级 print(climb_ways_variable_steps(10, [1, 3, 5]))5.2 变体二带障碍的爬山题目台阶数组arr表示山的情况arr[i] 1表示第i级台阶有障碍猴子不能停留在此台阶。求从山脚第0级假设总是安全的到山顶第N级的路径数。解析 这是带限制条件的动态规划。基本框架不变但需要在状态转移时增加判断。如果arr[i] 1则dp[i] 0。否则dp[i] dp[i-1] dp[i-2] dp[i-3]同时要保证i-1, i-2, i-3索引有效。同样可以优化空间。public static long climbWaysWithObstacles(int n, int[] arr) { // arr长度应为 n1, arr[0]表示起点通常为0无障碍 if (n 0 || arr[0] 1) return 0; if (n 1) return arr[1] 1 ? 0 : 1; long a 1; // dp[0] long b arr[1] 1 ? 0 : 1; // dp[1] long c 0; // 用于计算dp[2] long result 0; // 计算dp[2] if (n 2) { int waysTo2 0; if (arr[2] ! 1) { if (arr[1] ! 1) waysTo2 b; // 从第1级上来 waysTo2 a; // 从第0级跨2步上来 } c waysTo2; } if (n 2) return c; // 从第3级开始计算 for (int i 3; i n; i) { if (arr[i] 1) { result 0; } else { result 0; if (arr[i-1] ! 1) result c; if (arr[i-2] ! 1) result b; if (arr[i-3] ! 1) result a; } // 滚动更新 a b; b c; c result; } return result; }5.3 变体三最小体力消耗题目每级台阶有一个体力值cost[i]猴子站在该台阶上需要消耗对应体力。猴子从地面不消耗体力开始每次可以爬1或2级求爬到楼层顶部第N级台阶的上方的最小体力消耗。解析 这是LeetCode上经典的“爬楼梯最小成本”问题。定义dp[i]为到达第i级台阶并站在上面所花费的最小累计体力。注意终点是第N级的上方所以答案不是dp[N]而是min(dp[N-1], dp[N-2])因为可以从这两级直接跨到终点。 状态转移方程dp[i] cost[i] min(dp[i-1], dp[i-2])初始化dp[0] cost[0],dp[1] cost[1](因为可以从地面跨到第1级)。int minCostClimbingStairs(vectorint cost) { int n cost.size(); if (n 0) return 0; if (n 1) return cost[0]; // 实际上题目保证n2 vectorint dp(n, 0); dp[0] cost[0]; dp[1] cost[1]; for (int i 2; i n; i) { dp[i] cost[i] min(dp[i-1], dp[i-2]); } // 到达顶部的最后一步可以从倒数第一或倒数第二级跨上去 return min(dp[n-1], dp[n-2]); }6. 机试实战策略与避坑指南结合“猴子爬山”这道题我想分享一些在华为OD或其他公司机试中的通用策略和常见“坑点”。6.1 审题与沟通策略明确输入输出格式题目是输入一个整数N还是多组测试数据输出是单纯一个数字还是需要格式化务必看清。确认边界条件N的取值范围是多少(0 N 100 还是 1 N 10^5)。这直接影响你是否需要处理大数以及选择什么数据类型。理解问题本质“猴子爬山”本质是求方案数不是具体方案。如果要求打印所有具体方案那就是回溯算法了复杂度天差地别。6.2 编码过程中的关键检查点数组下标这是最最常见的错误来源。DP数组是声明为dp[n1]还是dp[n]循环是从0开始还是从1开始务必与你的状态定义保持一致。我的习惯是让dp[i]直接对应问题中的第i个状态如第i级台阶这样更直观通常需要n1的长度。初始化DP的初始化值是否正确对于“猴子爬山”dp[1], dp[2], dp[3]需要手动初始化。对于其他问题dp[0]往往很关键。整数溢出永远要对计算结果的大小有预估。如果题目没给模数如10^97而N可能很大果断使用long long(C) /long(Java) / Pythonint。空间优化写完基础DP后花一分钟思考是否能优化空间。像本题的滚动数组优化代码改动不大但能显著体现你的能力。6.3 测试用例设计不要只相信样例。自己设计几组测试用例边界用例n0,n1,n2,n3。较小普通用例n5(可以手算验证)。较大用例n30用优化DP和基础DP对比结果是否一致。性能用例n1000或n10000感受一下运行时间在本地IDE。6.4 关于代码风格在机试中代码风格是“隐形的加分项”。命名变量名、函数名要有意义。climbWays比solve好dp比arr好。注释在关键步骤如状态转移、初始化、边界处理加一行简短注释能让阅卷人或面试官快速理解你的思路。函数封装像我们这样把核心逻辑封装成函数main函数只负责输入输出结构清晰便于调试和阅读。错误处理虽然OJ输入通常规范但在函数开头对非法输入进行判断并返回如if n0 return 0体现了程序的健壮性。这道“猴子爬山”题就像一把钥匙打开的是动态规划乃至整个算法思维的大门。它的各种变体覆盖了面试中超过一半的DP考点。把这里的思路吃透再遇到“青蛙跳台阶”、“解码方法”、“不同路径”等问题时你会有一种豁然开朗的感觉。编程能力的提升没有捷径就是通过这样一道道经典题目的深入剖析和举一反三逐渐积累起来的。希望这篇长文能切实地帮到你。如果在实现过程中遇到任何问题或者对某个变体有新的想法欢迎随时交流。