从爬楼梯到动态规划：用Python和C++两种解法搞定OpenJudge上台阶问题

第一次接触动态规划时，很多人都会被那些抽象的状态转移方程搞得晕头转向。但如果你从最熟悉的爬楼梯问题入手，就会发现DP（动态规划）其实就藏在我们的日常思维中。记得我刚开始刷OpenJudge时，看到"上台阶"这道标着"递推"标签的题目，本能地写出了递归解法，却在提交时遭遇了时间限制和数值溢出的双重打击——这正是算法竞赛给我们上的第一课： 看似简单的问题背后，往往藏着精妙的优化空间 。

1. 问题本质与暴力递归解法

上台阶问题的描述简单得令人放松警惕：假设有n级台阶，每次可以跨1、2或3级，问有多少种不同的走法。就像站在教学楼楼梯口考虑今天的上楼方式，这种生活化的场景很容易让人忽略其中的计算复杂度。

1.1 问题建模与分析

让我们用数学语言重新表述这个问题。设f(n)为走上n级台阶的方法数，根据最后一步的跨法不同，可以分解为三种情况：

• 最后一步跨1级：前面走了f(n-1)种
• 最后一步跨2级：前面走了f(n-2)种
• 最后一步跨3级：前面走了f(n-3)种

于是得到递推关系：

f(n) = f(n-1) + f(n-2) + f(n-3)

边界条件是：

f(1)=1, f(2)=2, f(3)=4

1.2 Python递归实现

最直观的实现方式是递归，Python版本如下：

def climb_stairs(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    else:
        return climb_stairs(n-1) + climb_stairs(n-2) + climb_stairs(n-3)

这个解法虽然正确，但存在严重的性能问题。计算climb_stairs(30)时，你会发现明显的延迟——因为递归树呈指数级增长，存在大量重复计算。

小测试：尝试计算climb_stairs(35)，感受暴力递归的效率瓶颈

2. 记忆化优化：给递归装上缓存

2.1 记忆化原理

观察递归树会发现，同一个climb_stairs(k)会被计算无数次。记忆化技术（Memoization）的核心思想就是保存已经计算过的结果，避免重复计算。这就像做数学题时把中间结果写在草稿纸上，需要时直接查阅而不是重新计算。

2.2 Python记忆化实现

Python可以通过装饰器或字典轻松实现记忆化：

def memoize(f):
    memo = {}
    def helper(x):
        if x not in memo:            
            memo[x] = f(x)
        return memo[x]
    return helper

@memoize
def climb_stairs_memo(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    else:
        return climb_stairs_memo(n-1) + climb_stairs_memo(n-2) + climb_stairs_memo(n-3)

现在计算climb_stairs_memo(100)几乎是瞬间完成的，时间复杂度从O(3^n)降到了O(n)。

2.3 C++记忆化版本

C++中可以用静态数组或unordered_map实现记忆化：

#include <unordered_map>
using namespace std;

unordered_map<int, long long> memo;

long long climbStairs(int n) {
    if (memo.find(n) != memo.end()) return memo[n];
    if (n == 1) return 1;
    if (n == 2) return 2;
    if (n == 3) return 4;
    return memo[n] = climbStairs(n-1) + climbStairs(n-2) + climbStairs(n-3);
}

3. 递推解法：动态规划的终极形态

3.1 从递归到递推

记忆化递归是"自上而下"的解法，而递推则是"自下而上"的动态规划。我们从小问题开始，逐步构建大问题的解。对于上台阶问题，递推的实现尤为直观。

3.2 Python递推实现

def climb_stairs_dp(n):
    if n == 1: return 1
    if n == 2: return 2
    if n == 3: return 4
    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]

3.3 C++递推优化

C++版本需要注意数据类型的选用：

#include <iostream>
using namespace std;

long long dp[105]; // 必须用long long避免溢出

void precompute() {
    dp[1] = 1; dp[2] = 2; dp[3] = 4;
    for (int i = 4; i <= 100; ++i)
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
}

int main() {
    precompute();
    int x;
    while (cin >> x && x != 0) {
        cout << dp[x] << endl;
    }
    return 0;
}

关键点：

• 预处理所有可能查询的结果（题目最大n=100）
• 使用long long防止整数溢出（当n>36时int会溢出）
• 循环查询时直接输出结果，达到O(1)时间复杂度

4. 算法竞赛中的实战技巧

4.1 数据类型选择陷阱

在OpenJudge和NOI竞赛中，数据类型的选择经常是隐藏的坑点。对于上台阶问题：

台阶数n	f(n)值	int范围(约21亿)
36	2082876103	勉强不溢出
37	3831006429	已溢出

因此必须使用long long（64位整数，范围约9×10^18）才能正确处理n≤100的情况。

4.2 空间优化技巧

观察递推关系f(n) = f(n-1) + f(n-2) + f(n-3)，实际上只需要保存前三个状态：

def climb_stairs_opt(n):
    if n == 1: return 1
    if n == 2: return 2
    if n == 3: return 4
    a, b, c = 1, 2, 4
    for _ in range(4, n+1):
        a, b, c = b, c, a+b+c
    return c

C++版本同样适用这个优化，空间复杂度从O(n)降到了O(1)。

4.3 测试用例设计

在竞赛中设计全面的测试用例非常重要：

test_cases = {
    1: 1,
    2: 2,
    3: 4,
    4: 7,  # 1+2+4
    5: 13, # 2+4+7
    10: 274,
    20: 121415,
    36: 2082876103,  # int边界
    50: 10562230626642,
    100: 180396380815100901214157639
}

for n, expected in test_cases.items():
    assert climb_stairs_dp(n) == expected

5. 从特殊到一般的DP思维框架

上台阶问题虽然简单，但包含了动态规划的所有核心要素。我们可以从中提炼出解决DP问题的通用框架：

1. 定义状态 ：明确dp[i]表示什么（这里表示i级台阶的走法数）
2. 确定转移方程 ：找出状态间的关系（f(n)=f(n-1)+f(n-2)+f(n-3)）
3. 设置初始条件 ：给出最小子问题的解（f(1),f(2),f(3)）
4. 计算顺序 ：确定是从小到大递推还是递归+记忆化
5. 优化方向 ：考虑空间优化（如滚动数组）、预处理等

将这个框架应用到其他DP问题，比如：

• 背包问题（01背包、完全背包）
• 最长公共子序列
• 矩阵链乘法
• 股票买卖问题

在OpenJudge的实际比赛中，遇到DP问题时不妨先问自己：

• 这个问题的最优子结构是什么？
• 状态转移的可能路径有哪些？
• 边界条件如何处理？
• 数据规模是否需要注意溢出？

最后分享一个实战技巧：在比赛环境里，可以预先计算并打印出小规模的结果，既能验证算法正确性，也能帮助发现潜在的边界条件问题。比如先输出1-10的f(n)值，确保基本逻辑无误后再处理大规模输入。