楼梯递归

我试图理解一本书中提供的以下问题的解决方案：

“一个孩子正在跑上有 n 级台阶的楼梯，并且一次可以跳 1 级、2 级或 3 级。实现一种方法来计算孩子可以跑上楼梯的可能方式。”

书中的解决方案如下，源于“最后一步可能是从n - 1开始的单步跳跃，从步骤n - 2开始的双步跳跃或从步骤n - 3开始的三步跳跃”

public static int countWaysDP(int n, int[] map) {
    if (n < 0) 
        return 0;
    else if (n == 0)
        return 1;
    else if (map[n] > -1)
        return map[n];
    else {
        map[n] = countWaysDP(n - 1, map) + countWaysDP(n - 2, map) + countWaysDP(n - 3, map);
        return map[n]; }
}

我的困惑是：

1. 如果步数为零，为什么程序要返回 1？我的想法是，如果步数为零，那么穿过楼梯的方式就有零种。难道不是更好的解决方案是“if (n

2. 我不确定我是否理解将其设为静态方法背后的基本原理？ Google 表示静态方法是由整个类调用的方法，而不是由类的对象调用的方法。所以这本书的意图似乎是这样的：

.

class Staircase {
    static int n;
public:
    static int countWaysDP(int n, int[] map); }

代替：

class Staircase {
    int n;
public:
    int countWaysDP(int n, int[] map); }

为什么？类实例化多个楼梯有什么问题？

Thanks.

（注：本书正在破解编码面试）

回答你的第一个问题，这就是数学之美：如果楼梯有 1 级台阶，就有 1 种解决方法。如果有0步，还有1种解决方法，就是什么都不做。

就好像，对于一个n级楼梯，m次，你可以走1、2或3级台阶来完成它。因此，如果 n 为 1，则 m 为 1，并且有 1 种方式。如果n为0，m为0，还有一种方法——根本不采取任何步骤。

如果你写出两级楼梯的所有路径，那就是[[1, 1], [2]]，对于 1 级楼梯，它是[[1]]，对于 0 楼梯，它是[[]], not []。数组内部元素的数量[[]]是 1，不是 0。

如果问题是您可以走 1 步或 2 步，这将成为斐波那契数列。请注意，fib(0) = 1 和 fib(1) = 1，它对应于同一件事：当楼梯为 1 步时，有 1 种解决方法。当有 0 个步骤时，有 1 种方法可以解决，那就是什么都不做。事实证明，走两级楼梯的方式数 fib(2) 是 2，它等于 fib(1) + fib(0) = 1 + 1 = 2，如果 fib( 0) 等于 0。