爬楼梯问题：计算1/2/3步登顶路径数及组合思路验证

你的组合数学思路是否正确？ #

你的思路是正确的，更精准的表述如下：

爬楼梯的路径本质是由若干个1、2、3组成的有序序列，序列元素之和等于n（每个元素代表单步爬的台阶数）。对应到组合数学模型：

• n个不可区分的“台阶”是待分配的物体
• 每个“步数”对应一个可区分的盒子（因顺序不同路径不同，盒子具有顺序属性）
• 每个盒子最多容纳3个物体（对应单步最多爬3级台阶）
• 对于每一组满足 m + 2p + 3q = n 的非负整数组合（m是1级步数的数量，p是2级步数的数量，q是3级步数的数量），计算该组合的排列数 (m+p+q)! / (m!p!q!)，将所有组合的排列数相加，结果即为总路径数。

以n=3为例验证：

• 组合(3,0,0)：排列数为 3!/(3!0!0!)=1，对应路径(1,1,1)
• 组合(1,1,0)：排列数为 2!/(1!1!0!)=2，对应路径(1,2)、(2,1)
• 组合(0,0,1)：排列数为 1!/(0!0!1!)=1，对应路径(3)
  总和1+2+1=4，与示例结果一致。

递归函数实现 #

按照题目要求，递归函数的核心逻辑基于递推关系：爬完n级台阶的总路径数，等于爬n-1级的路径数（最后一步爬1级）、爬n-2级的路径数（最后一步爬2级）、爬n-3级的路径数（最后一步爬3级）之和。边界条件处理：

• n=0时，视为有1种方法（不爬）
• n<0时，无可行路径，返回0

Python实现代码：

def steps(n):
    if n == 0:
        return 1
    if n < 0:
        return 0
    return steps(n-1) + steps(n-2) + steps(n-3)

测试示例：steps(3)返回4，steps(5)返回13，均符合预期。

两种思路的联系 #

组合数学思路是从“枚举所有合法步数组合并计算排列数”的角度直接求解，递归思路则通过递推关系高效计算结果，二者本质等价——递归的递推式其实是组合数学求和的另一种表达形式。需要注意的是，基础递归版本未做记忆化优化，对于较大的n会存在大量重复计算，若需优化可添加缓存，但题目仅要求递归函数，基础版本即可满足要求。

内容的提问来源于stack exchange，提问作者Soham