DP 数组第 0 个元素初始化为 1 而不是 0

Question

在使用以下解决方案（取自https://emre.me/coding-patterns/staircase/）解决爬楼梯问题（请参阅此处）时，我假设 dp 数组的每个值表示可以采取的方式数量达到那一步。

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 数组中的第 0 个元素初始化为 1 而不是 0？谁能解释一下它的逻辑？

如果我使用 dp[0]=0，它在递归/数组实现中工作正常，但对于 dp，它始终仅适用于 dp[0]=1

Answer 1

原因是总是至少有一种方法可以到达楼梯顶部。如果楼梯没有楼梯（n = 0），那么还有一种方法可以爬楼梯，即不走台阶。请注意，重要的不是到达顶部的步数（这里为零），而是路数（仍然是 1）。