如何修改斐波那契数列问题？

Question

我试图找出如何修改下面的代码来帮助解决给定的问题。但是，我不是一次只能走1到2步，而是想让自己也能走3步。你知道吗

你有一个N级的梯子。你可以一次走一步或两步，任何一种方式都可以爬上梯子。有多少条不同的路线（一步或两步的组合）组成梯子？你知道吗

下面是我试图修改的一些代码：

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行对于第一个问题是正确的，但是对于第二个问题不是。记住，结果应该是你可以走的可能路线的数量。你知道吗

如果你一次可以走一步或两步，那么当你剩下一个横档时，只有一件事可以做：走一步。如果你还有两个梯级，你有两个选择：要么走两步，要么走一步（一个梯级），然后走另一步（第二个梯级）。所以，在某种程度上，对于这个版本的问题，基本情况下的路由数恰好等于剩余的横档数。你知道吗

如果您一次可以走一步、两步或三步，那么当您还有三个梯级时，路由的数目不是三个；有三个以上的选项。您必须计算有多少个选项，并在n == 3的情况下返回。你知道吗

Answer 2

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

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

代码如下：

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