主页 / coding / 问题 / 79371937
Accepted
ABGR
Asked: 2025-01-21 00:02:52 +0800 CST

通过一次爬一级、两级或三级台阶到达 A 点到 B 点的方法数

  • 772

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

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 步。

这也造成了一些混乱。

algorithm

1 个回答

  1. Best Answer

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

    是的。

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

    是的，或者您可以更轻松地添加案例，因为它代表您到达目的地的n == -1情况，并代表可能性 (1)。这看起来很奇怪，但与您之前的观察一致，即这个问题的表述方式与您更习惯的措辞相比有 1 步不同。情况是您超出目的地的情况，因此这就是您想要返回 0 的时候。实际上，除了准确到达（ ）和超出（ ）之外，您不需要其他情况。其余的由此得出。n < -1n == -1n < -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 = 0; 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 = 0; n < 5; n++) {
    console.log(n, countWays(n));
}

    • 1

相关问题