我该如何修改这个斐波那契数列问题？

Question

我想知道如何修改下面的代码来帮助解决给出的问题。但是，我不想一次只能走 1 或 2 步，我想做到这样我也可以走 3 步。

您有 N 步（梯级）的阶梯。您可以通过任意组合一次走 1 步或两步走上梯子。有多少条不同的路线（1 步或 2 步的组合）可以组成阶梯？

这是我要修改的一些代码：

def countP(n):
    if (n == 1 or n == 2):
        return n

    return countP(n-1) + countP(n-2)

到目前为止我已经试过了，但我没有得到正确的答案：

def countP(n):
    if (n == 1 or n == 2 or n == 3):
        return n

    return countP(n-1) + countP(n-2) + countP(n-3)

任何指导的帮助都会有很大的帮助！谢谢

Answer 1

return n 行对第一个问题是正确的，但对第二个问题不正确。请记住，结果应该是您可以选择的可能路线的数量。

如果您一次可以迈出一步或两步，那么当您还剩一个梯级时，您只能做一件事：迈出一步。如果还剩两个梯级，您有两个选择：要么走两步，要么迈出一步（一个梯级），然后再迈一步（第二个梯级）。因此，有点巧合的是，对于这个版本的问题，基本案例中的路线数量恰好等于剩余的梯级数量。

如果你一次可以走一步、两步或三步，那么当你还剩三个梯级时，路线数就不是三条；有三个以上的选项。您将不得不计算有多少选项，并且 return 在 n == 3.

的情况下

Answer 2

你在 n = 3 递归中的基本情况是错误的。
对于 n = 3，正确答案应该是 4，但您返回的是 3。
我建议您使用以下观察结果来简化基本情况：

最基本的情况是 n <= 1，即当我们只有一个楼梯或没有楼梯时，因此唯一的攀登方式是走 1 个单位或 0 个单位。因此，方式的数量是 countP(0) = 1 和 countP(1) = 1.
当 n > 1 时会发生什么？
好吧，第一步我们有三个选择 - 我们可以采取 m 个单位（1 个单位、2 个单位或 3 个单位步骤）作为第一步提供 m <= n。
如果我们可以将 1 个单位步骤作为第一步，我们可以将子问题从 countP(n) 减少到 countP(n-1).
如果我们可以采取 2 个单位步长作为第一步，我们可以将子问题从 countP(n) 减少到 countP(n-2).
如果我们可以采取 3 个单位步骤作为第一步，我们可以将子问题从 countP(n) 减少到 countP(n-3)。
因此，我们的最终计数将是：所有 m <= n

countP(n - m)

代码如下：

def countP(n):
    if (n == 0 or n == 1):
        return 1

    count = 0
    for m in [1, 2, 3]:
        if m <= n:
            count += countP(n - m)

    return count

我该如何修改这个斐波那契数列问题？

How do I modify this Fibonacci Sequence Problem?

python

sequence

fibonacci