python - 如何修改这个斐波那契数列问题？

Question

我试图弄清楚如何修改下面的代码来帮助解决给出的问题。但是，我不想一次只能执行 1 或 2 步，而是希望能够同时执行 3 步。

你有一个 N 级台阶(横档)的梯子。您可以一次走 1 步或走 2 步，以任意组合的方式爬上梯子。有多少种不同的路线(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

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 .
   如果我们可以将 1 个单位步作为第一步，我们可以将子问题从 countP(n) 减少。至countP(n-1) .
   如果我们可以将 2 个单位的步长作为第一步，我们就可以将 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