一次爬一级、两级或三级台阶到达A到B的方式数

Question

我正在在线平台上解决一个测试，问题陈述与此类似。

Stuart 必须从一个地方走到另一个地方（A->B），他可以一次跳 1 步、2 步或 3 步。 A 到 B 之间可以有 n 个塞子。

我们需要找到他可以做到这一点的方法的数量。

我觉得这与经典的爬楼梯问题类似，几乎没有什么区别，你最终必须到达第 n 级台阶，而在这个特定问题中，你必须下来，这可能导致 n+1 级台阶。我说得对吗？

所以我写的代码是这样的：

function countWays(n) {
    
    if (n < 0) return 0;
    if (n === 0) return 1;
    if (n === 1) return 2; //If you have one stop-over, there's two ways to reach. One is take one jump and then one more. Second is take two jumps at once and reach the destination

    return countWays(n-1) + countWays(n-2) + countWays(n-3);
 
}

console.log(countWays(4))

这没有被接受。所以我只是想知道这出了什么问题。我是否也应该为

n==2

添加基本案例？

if (n === 2) return 4

这仍然没有任何好处，但至于

n = 3

，它会返回

6

，而从视觉上我可以看到，如果有3次中途停留，就会有7种方式。

我想问的另一个问题是，

在经典的楼梯案例中，

n === 0

的基本情况为 1。这里是否仍然相同？这让我有点困惑，因为当没有更多的台阶可以爬时，结果怎么会是 1。在手上，当

n === 1

你仍然有一条路必须走才能到达目的地。

此外，对于

f(3)

，逻辑和直觉表明它应该是：

number of ways to reach first stopover + f(2)

并且

number of ways to reach first stopover

只是其中之一，因为只有一种方法可以做到这一点（跳一跳。）

但是，我不能将

if(n == 1) return 1

放在基本情况中，因为它是不正确的。假设只有一个中转站 (n = 1)，实际上有两种方法可以到达：

1. 跳2步
2. 跳 1 步，然后再跳 1 步。

所以这也造成了一些混乱。

Answer 1

我觉得这类似于经典的爬楼梯问题……而在这个特定的问题中，你必须下来，这可能需要 n+1 步。我说得对吗？

是的。

我是否也应该添加 n==2 的基本情况？

是的，或者您可以更轻松地添加

n == -1

情况，因为它代表您 到达 目的地的情况，并且代表可能性 (1)。这看起来很奇怪，但这与您之前的观察结果一致，即与您更习惯的措辞相比，该问题的表述方式与 1 步骤不同。

n < -1

的情况就是你超调目的地，所以这就是你想要返回0的时候。除了准确到达（

n == -1

）和超调（

n < -1

）之外，你实际上不需要其他情况）。其余的都随之而来。

这是您的代码：

function countWays(n) {
    if (n < -1) return 0; // Overshooting: not a possibility.
    if (n === -1) return 1; // Destination reached: this is a possibility and thus counts as one.
    return countWays(n-1) + countWays(n-2) + countWays(n-3);
}

for (let n = 1; n < 5; n++) {
    console.log(n, countWays(n));
}

现在这效率不高，对于较大的

n

，你将一遍又一遍地进行相同的递归调用。您可以使用自下而上的制表来获得有效的解决方案：

function countWays(n) {
    let [a, b, c] = [0, 0, 1];
    while (n-- > -1) {
        [a, b, c] = [b, c, a + b + c];
    }
    return c;
}

for (let n = 1; n < 5; n++) {
    console.log(n, countWays(n));
}