LeetCode爬楼梯问题：为何DP数组dp[0]初始化为1而非0？

问题背景 #

LeetCode爬楼梯问题描述：

你正在爬楼梯，需要n阶才能到达楼顶。每次你可以爬1或2个台阶。问有多少种不同的方法爬到楼顶？
示例：输入n=3，输出3，对应三种爬楼方式：1+1+1、1+2、2+1。约束条件：1<=n<=45。

你提到的动态规划解法代码如下：

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0 for x in range(n+1)]
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

核心疑问解答 #

首先明确dp[i]的定义：到达第i阶台阶的不同路径数。

为什么dp[0]必须设为1？ #

这是为了让递推公式dp[i] = dp[i-1] + dp[i-2]在所有i≥2的场景下都成立，属于边界条件的数学补全约定：

• 当计算dp[2]时，公式展开为dp[1] + dp[0]。dp[1]是到达第1阶的路径数（只有1种：直接爬1阶）；而dp[0]对应的是“从第0阶直接爬2阶到第2阶”的路径数——这里的第0阶可以看作是起点前的虚拟位置，站在这个位置，有一种“到达”它的方式（就是不移动，空操作），所以这种爬2阶的路径数就是1，正好对应dp[0]=1。
• 如果把dp[0]设为0，那么dp[2] = 1 + 0 = 1，但实际到达第2阶有2种路径（1+1、直接爬2阶），结果明显错误。因此必须将dp[0]设为1，才能保证递推逻辑的正确性。

为什么递归实现中dp[0]可以设为0？ #

这是因为递归的终止条件定义和DP的递推逻辑存在细微差异：

• 很多递归实现会将终止条件设为：当n=1时返回1，当n=2时返回2，此时递归不会触及n=0的情况；如果递归逻辑需要处理n=0，有些实现会把它定义为“不需要爬台阶，没有路径”，但这是对问题场景的窄化定义——而DP实现是通过统一的递推公式覆盖所有情况，因此需要用dp[0]=1来补全边界，让公式从i=2开始就生效。

举个更直观的例子：

• 当n=2时，DP公式计算得dp[2] = 1 + 1 = 2，完全符合实际路径数；
• 若dp[0]=0，计算结果为1，与实际不符，这也直接证明了dp[0]=1的必要性。

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