1. 项目概述：从“猴子爬山”到动态规划思想

最近在辅导一些准备华为OD机考的朋友，发现“猴子爬山”或者说“上N阶台阶”这类题目出现的频率相当高，尤其是在B卷和C卷中，经常作为100分的大题出现。这题乍一看是个简单的数学问题或者递归问题，但如果你只停留在“有多少种爬法”这个层面，那在机考的高压环境下，大概率是要超时甚至爆内存的。它本质上是一个绝佳的动态规划入门案例，考察的是你能否将生活问题抽象成数学模型，并用高效的算法去解决它。很多刚接触算法的新手，包括一些有几年业务开发经验但疏于算法练习的朋友，很容易在这里栽跟头——要么递归写得层层嵌套，指数级复杂度直接让程序卡死；要么思路混乱，状态转移方程写不出来。

我自己当年准备类似考试时，也在这类题目上花了不少功夫。它的核心价值在于，用一个非常具象的场景（爬台阶），引出了计算机科学中一个极其重要的思想：动态规划。掌握了它，你不仅能轻松应对这道题，更能触类旁通，解决一大类“计数”、“最优解”问题，比如硬币找零、背包问题、最长公共子序列等。所以，今天我们就以C++为例，不光是解出这道题，更要深挖背后的“为什么”，把动态规划的思路、优化技巧以及编码中那些容易踩的坑，一次性讲透。无论你是正在备战华为OD，还是在学习算法与数据结构，这篇文章都能给你提供一条清晰的实践路径。

2. 问题深度解析与抽象建模

2.1 问题原貌与关键约束

我们先来明确一下题目通常的描述。一个经典的版本是：“一只猴子要爬一个有N阶的台阶，它一次可以爬1阶、2阶或3阶。问猴子爬上这个台阶总共有多少种不同的方法？”

这里有几个关键点需要立刻抓住：

1. 目标 ：求的是“方法总数”，是一个计数问题，不是求具体路径。
2. 操作（选择） ：猴子每一步有3种选择：上1阶、上2阶或上3阶。这是状态转移的基础。
3. 顺序重要性 ：先跳1阶再跳2阶，和先跳2阶再跳1阶，是两种不同的方法。这说明我们关心步骤的序列，是排列问题而非组合问题。
4. 边界条件 ：当台阶数为0时，通常认为有一种方法（“不动”或“已经到达”）。当台阶数小于0时，方法数为0。

如果仅仅理解到这里，很多人会直接写出递归函数： f(n) = f(n-1) + f(n-2) + f(n-3) 。这个思路完全正确，但它就像一把没开刃的刀，直接用来砍树效率极低。我们需要深入分析其复杂度。

2.2 从递归到动态规划的思想跃迁

为什么朴素的递归不行？我们来画一下递归树（以n=5为例）：

                        f(5)
                      /   |   \
                f(4)     f(3)    f(2)
               / | \     / | \    / | \
          f(3) f(2) f(1) ... (以此类推)

你会发现， f(3) 、 f(2) 等函数被重复计算了无数次。时间复杂度是近似 O(3^n) 的指数级，当n稍微大一点（比如50），计算量就是天文数字，必然超时。

动态规划的核心思想就在于“避免重复计算”。它有两种等价的实现思路：

• 自顶向下的记忆化搜索 ：在递归的基础上，增加一个“备忘录”（数组或哈希表），每次计算 f(n) 前先查表，如果算过就直接返回结果，否则再递归计算并存入表中。这本质是递归的优化。
• 自底向上的递推 ：这是我们更推崇的、在机考中更稳妥的方法。我们从最小的子问题开始解： f(0)=1, f(1)=1, f(2)=2 。然后利用状态转移方程 f(n) = f(n-1) + f(n-2) + f(n-3) ，从3开始一路递推到n。这样每个状态只计算一次，时间复杂度是完美的 O(n)。

注意 ：在机考环境中， 强烈推荐使用自底向上的递推法 。理由有三：1) 代码结构简单，不易出错；2) 运行效率稳定，没有递归函数调用的开销和栈溢出风险；3) 思维模式更贴近动态规划的经典教学，方便你应对变种题。

2.3 状态定义与转移方程的再思考

对于这道题，状态定义非常直接： dp[i] 表示爬上 i 阶台阶的方法总数。 状态转移方程就是： dp[i] = dp[i-1] + dp[i-2] + dp[i-3] ，其中 i >= 3 。

这里有一个 极易出错 的细节：初始化的值。根据我们的定义：

• dp[0] = 1 ：没有台阶，可以视为一种方法（通常这样定义能使转移方程在 i=1,2,3 时也成立）。
• dp[1] = 1 ：只有一阶台阶，只有一种方法（爬1阶）。
• dp[2] = 2 ：有两阶台阶，有两种方法（1+1， 或直接2）。

你可以验证一下， dp[3] = dp[2] + dp[1] + dp[0] = 2+1+1=4 ，这与实际情况（方法：111，12，21，3）吻合。

3. C++实现详解与代码打磨

理解了原理，我们来看C++的实现。这里我会给出两个版本的代码，并详细解释每个版本的设计考量和避坑点。

3.1 基础版本：清晰但需注意溢出

这是最直接的实现，适合在笔试时快速写出。

#include <iostream>
#include <vector>
using namespace std;

long long climbStairs(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    if (n == 2) return 2;

    vector<long long> dp(n + 1, 0);
    dp[0] = 1; // 边界条件
    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }

    return dp[n];
}

int main() {
    int N;
    cout << "请输入台阶数 N: ";
    cin >> N;
    long long ways = climbStairs(N);
    cout << "总共有 " << ways << " 种方法。" << endl;
    return 0;
}

代码要点与避坑指南：

1. 数据类型选择 - long long ：这是第一个大坑！当N较大时（比如N=50），方法数会是一个巨大的整数，远超 int 的范围（约21亿）。使用 int 会导致溢出，得到错误结果。 long long 可以表示更大范围的整数。在华为OD的评测系统中，通常也会考察对大数的处理，所以养成使用 long long 的习惯很重要。
2. 数组大小 - vector<long long> dp(n + 1, 0) ：我们声明了 n+1 个元素，因为我们需要访问 dp[n] 。下标从0到n，总共n+1个。初始化所有值为0是个好习惯。
3. 边界处理 ：函数开头对 n<=0, n==1, n==2 进行了特判。虽然我们的dp数组也能处理，但提前返回可以使逻辑更清晰，并且当n很小时避免不必要的数组创建开销。 dp[0]=1 是这个递推关系成立的关键，务必理解。
4. 循环从3开始 ：因为 dp[0], dp[1], dp[2] 我们已经手动初始化了，它们是递推的“基石”。

3.2 优化版本：滚动数组节约空间

基础版本的空间复杂度是 O(n)。我们观察到，在计算 dp[i] 时，只依赖于前三个状态 dp[i-1], dp[i-2], dp[i-3] 。我们完全不需要保存整个数组，只用三个变量滚动更新即可。这在处理超大N（比如上亿，虽然本题不太可能）或对内存有严格限制的场景下很有用。

#include <iostream>
using namespace std;

long long climbStairsOptimized(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    if (n == 2) return 2;

    long long a = 1; // 代表 dp[i-3]，初始为 dp[0]
    long long b = 1; // 代表 dp[i-2]，初始为 dp[1]
    long long c = 2; // 代表 dp[i-1]，初始为 dp[2]
    long long ways = 0;

    for (int i = 3; i <= n; ++i) {
        ways = a + b + c; // 计算 dp[i]
        // 滚动更新，为下一次迭代准备
        a = b;
        b = c;
        c = ways;
    }
    // 循环结束时，c 或 ways 存储的就是 dp[n]
    return c;
}

int main() {
    int N;
    cout << "请输入台阶数 N: ";
    cin >> N;
    long long ways = climbStairsOptimized(N);
    cout << "总共有 " << ways << " 种方法。" << endl;
    return 0;
}

优化点解析：

• 空间复杂度从 O(n) 降至 O(1) ：只用了4个 long long 变量，与n无关。
• 变量命名与滚动逻辑 ： a, b, c 分别对应三个历史状态。在每次循环中，计算新值后，通过 a=b; b=c; c=ways; 这条语句优雅地完成状态的“滚动”。想象一下这三个变量像一个滑动窗口，在时间序列上向前移动。
• 返回值 ：循环结束后，最新的结果存储在 c （或 ways ，此时两者相等）中，直接返回即可。

实操心得 ：在机考中，如果题目没有明确的空间限制， 使用基础版本（ vector ）通常更稳妥 。因为它思路直观，不易在索引和更新上出错。优化版本虽然漂亮，但在紧张的考试环境下，万一滚动更新那几步写错了，调试起来更耗时。先求正确，再求优化。

4. 核心环节：动态规划思维的通用化训练

“猴子爬山”问题是一个完美的模板。掌握了它，你可以轻松解决一系列变种问题。关键在于如何调整“状态定义”和“转移方程”。

4.1 变种一：每次能爬的阶数变化

题目 ：如果猴子一次可以爬1阶、2阶、3阶……直到k阶呢？ 解法 ：状态转移方程变为： dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-k] ，其中 i >= k 。初始化时，需要计算出 dp[0] 到 dp[k-1] 的所有值。这时，使用基础版本的数组方法会更方便，因为需要累加的前置状态变多了。

// 假设最多一次爬k阶
long long climbStairsK(int n, int k) {
    vector<long long> dp(n + 1, 0);
    dp[0] = 1; // 基石
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= k && j <= i; ++j) { // 注意j不能超过i
            dp[i] += dp[i - j];
        }
    }
    return dp[n];
}

4.2 变种二：带有障碍的台阶（爬楼梯问题LeetCode 70进阶）

题目 ：台阶上有一些障碍物，标记为1，猴子不能踩上去。求有多少种方法爬到顶部？ 解法 ：状态定义不变，但转移时需要判断。如果第i阶是障碍物，则 dp[i] = 0 。否则， dp[i] = dp[i-1] + dp[i-2] + dp[i-3] ，当然也要保证 i-1, i-2, i-3 是合法的下标。这引入了“状态可行性”的判断。

4.3 变种三：最小花费爬楼梯（LeetCode 746）

题目 ：每阶台阶有一个“体力花费”，猴子每次爬1阶或2阶，求爬到顶部的最小总花费。 解法 ：状态定义需要变化。 dp[i] 可以定义为“到达第i阶台阶的最小花费”。注意，这里“到达”意味着站在第i阶上。转移方程： dp[i] = min(dp[i-1], dp[i-2]) + cost[i] 。初始化 dp[0] = cost[0], dp[1] = cost[1] 。最终答案不是 dp[n] ，而是 min(dp[n-1], dp[n-2]) ，因为顶部是第n阶，可以从n-1或n-2阶跨上去。

通过以上变种，你会发现，动态规划就像搭积木：

1. 定义状态 ： dp[i] 代表什么？是方法数、最小花费、最大收益？
2. 确定转移方程 ：当前状态 dp[i] 如何由之前的状态 dp[j] (j < i) 推导出来？
3. 初始化 ：最基础的、无法由其他状态推导的状态（如 dp[0], dp[1] ）是多少？
4. 确定计算顺序 ：通常是自底向上，从小i算到大i。
5. 得到答案 ：最终答案对应哪个状态？ dp[n] ？还是 max(dp[...]) ？

5. 机考实战技巧与常见“坑点”实录

结合华为OD机考的环境和这道题的特点，我总结了几条血泪教训：

5.1 输入输出处理

机考系统通常是标准输入输出。你的代码必须能正确读取题目提供的输入。对于本题，输入通常就是一个整数N。

• 坑点1：多组测试数据 。题目有时会说“输入包含多组测试用例”。这时你需要用 while(cin >> N) 这样的循环来读取，直到文件结束。

  int N;
  while (cin >> N) {
      cout << climbStairs(N) << endl;
  }
  

• 坑点2：输入格式不明确 。有时输入可能带有描述，如 “N=5” 。你需要用字符串处理或 scanf(“N=%d”, &N) 来精确读取。 务必仔细读题！

5.2 时间与空间复杂度估算

在写代码前，心里要对复杂度有数。

• 对于基础DP解法，时间复杂度 O(n)，空间复杂度 O(n) 或 O(1)。对于n最大为1000甚至10000的量级，都完全没问题。
• 如果你错误地写了朴素递归，当n=30时可能就会感到明显延迟，n=50基本必定超时。机考系统会返回“运行超时”或“TLE”错误。

5.3 调试与测试用例设计

在本地或机考系统的调试环节，不要只测一个例子。

• 必测用例 ：
  • N=0 ：返回0还是1？根据题目定义来，我们的代码返回0（因为特判 n<=0 返回0）。但有些题目规定0阶有1种方法，需要调整。
  • N=1 ， N=2 ：测试边界。
  • N=3 ：验证 dp[3]=4 。
  • N=10 或 N=20 ：手算或找已知结果验证。
  • 大数测试 ： N=50 。用你的程序跑一下，结果应该是一个很大的数。你可以用一个在线的、能处理大整数的计算器（或写个Python脚本）验证前几项，确保递推关系正确。重点检查是否溢出。

5.4 代码风格与容错

• 使用 long long ：我已经强调多次了，这是整数溢出问题的唯一解药。
• 初始化变量 ：特别是使用滚动数组时，确保 a, b, c 在循环开始前被正确赋值。
• 函数封装 ：将核心逻辑写在 climbStairs 函数里， main 函数只负责输入输出。这样结构清晰，也便于测试。
• 添加必要注释 ：对于关键步骤，如状态初始化、转移方程、滚动更新，可以加简短注释。这不会扣分，反而在思路不清时能帮你理清逻辑。

6. 从本题延伸的算法学习建议

如果你能轻松搞定这道题，那么你已经推开了动态规划的大门。接下来可以按这个顺序继续深入：

1. 经典一维DP ：

   • 斐波那契数列 ： dp[i] = dp[i-1] + dp[i-2] ， 和本题几乎一样，是更简单的版本。
   • 最大子数组和（LeetCode 53） ： dp[i] 定义为“以第i个元素结尾的最大子数组和”，转移方程 dp[i] = max(nums[i], dp[i-1] + nums[i]) 。这是理解“状态定义如何影响问题求解”的绝佳例子。
   • 打家劫舍（LeetCode 198） ： dp[i] 表示偷窃前i间房屋能获得的最大金额，状态转移需要考虑是否偷第i间。

2. 经典二维DP ：

   • 不同路径（LeetCode 62） ： dp[i][j] 表示到(i,j)点的路径数， dp[i][j] = dp[i-1][j] + dp[i][j-1] 。这是二维网格上的计数问题。
   • 01背包问题 ：这是动态规划的里程碑。理解 dp[i][j] 表示“考虑前i件物品，在容量为j的背包下的最大价值”，以及“放”与“不放”的状态转移。

3. 记忆化搜索 ： 回头再看“猴子爬山”，尝试用“自顶向下”的记忆化搜索（递归+备忘录）实现一遍。这能帮助你理解DP的两种实现方式本质上是相通的，并且在处理某些状态转移不那么直观的问题（如树形DP）时，记忆化搜索的思维模式会更自然。

最后，我个人最深刻的体会是，学习算法切忌死记硬背代码。像“猴子爬山”这样的题，要抓住其本质—— 将大问题分解为重叠子问题，并存储子问题的解 。每遇到一道新题，都强迫自己按照“定义状态 -> 推导转移 -> 确定初值 -> 计算顺序 -> 获取答案”这五步去思考。开始时可能很慢，但坚持下来，你会发现很多难题都不过是几个经典模型的组合与变种。在华为OD这类限时机考中，这种系统化的思维训练，远比刷海量题目却不得要领要有效得多。