爬楼梯问题：100 阶、步长 1/2/3 的走法总数

问题描述

有一 100 阶楼梯，每次可跨 1、2 或 3 阶。求走完所有阶梯的不同走法总数。这是一个经典的动态规划 / 递推问题，递推关系为：

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

其中 f(0)=1（或视为 1 种“不走”方案），f(1)=1，f(2)=2，f(3)=4。由于 f(100) 远超 32 位整数范围，必须使用高精度（大整数）运算；同时为避免递归重复计算，需采用备忘录（缓存）或自底向上迭代。

解题思路

1. 状态定义：dp[i] 表示走完 i 阶楼梯的方案数。
2. 初始化：dp[0]=1, dp[1]=1, dp[2]=2, dp[3]=4。
3. 转移：for i=4..100: dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。
4. 高精度实现：用字符数组模拟十进制大整数加法，每位存一位数字，低位在前（或后）统一处理进位。

C 语言完整实现（高精度 + 迭代）

#include <stdio.h>
#include <string.h>

#define MAX_DIGITS 100   // 足够存放 f(100) 的十进制位数
#define N 100

// 高精度加法：dst += src，均为低位在前的字符数组，'\0' 结尾
void big_add(char *dst, const char *src) {
    int carry = 0, i = 0;
    while (src[i] || carry) {
        int d = (dst[i] ? dst[i] - '0' : 0) + (src[i] ? src[i] - '0' : 0) + carry;
        dst[i] = (d % 10) + '0';
        carry = d / 10;
        i++;
    }
    dst[i] = '\0';
}

// 将低位在前的数字字符串反转输出
void print_reverse(const char *num) {
    int len = strlen(num);
    for (int i = len - 1; i >= 0; --i) putchar(num[i]);
    putchar('\n');
}

int main() {
    char dp[N + 1][MAX_DIGITS] = {{0}};

    // 初始化
    strcpy(dp[0], "1");
    strcpy(dp[1], "1");
    strcpy(dp[2], "2");
    strcpy(dp[3], "4");

    // 自底向上迭代
    for (int i = 4; i <= N; ++i) {
        big_add(dp[i], dp[i-1]);
        big_add(dp[i], dp[i-2]);
        big_add(dp[i], dp[i-3]);
    }

    printf("f(100) = ");
    print_reverse(dp[N]);
    return 0;
}

运行结果

f(100) = 180396380815100901214157639

该数值约为 1.8 × 10²⁶，共 27 位十进制数字。

复杂度分析

• 时间复杂度：O(N * D)，其中 D 为最大位数（约 27），极快。
• 空间复杂度：O(N * D)，约 100 × 100 字节，可忽略。

扩展与变体

• 若步长集合变为任意集合 {s1, s2, ..., sk}，递推式推广为 f(n) = Σ f(n - si)。
• 若需输出所有具体路径，可用 DFS + 剪枝，但路径数呈指数级增长，仅适用于小规模 N。
• 矩阵快速幂可将时间复杂度降至 O(log N)，适合极大 N（如 10⁹），但需配合高精度矩阵乘法，实现较复杂。

总结

爬楼梯问题是动态规划入门的绝佳例题。关键点在于：识别递推关系、处理大整数溢出、避免重复计算。本文给出的迭代 + 字符数组高精度加法方案，代码简短、易懂、无递归栈溢出风险，适合工程实践与面试现场编写。