您在n = 3
的递归中的基本情况是错误的。对于n = 3
,正确答案应该是4
,但是您将返回3
。我建议您通过使用以下观察来简化基本情况:
我试图弄清楚如何修改下面的代码来帮助解决所给出的问题。但是,我想做到这一点,而不是一次只能执行1或2步,所以我也可以采取3步。
您有N步梯(梯级)。您可以一次梯级或两步任意组合地爬上梯子。要组成阶梯,有多少种不同的路线(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)
任何指导帮助都将大有帮助!谢谢
第return n
行对第一个问题正确,但对第二个问题不正确。请记住,结果应该是您可以采取的可能路线数量。
如果您一次只能执行一两个步骤,那么当您剩下一档时,您只需要做一件事:迈出一步。如果还剩两个梯级,则有两个选择:要么走两步,要么走一个步骤(一个梯级),然后走另一步(第二个梯级)。因此,从某种程度上讲,是出于巧合,对于此版本的问题,基本情况下的路由数恰好等于剩余的梯级数。]
如果您一次可以执行一,二或三步,那么剩下三个梯级时的路径数就不会是三;有三个以上的选择。您将不得不计算有多少个选项,并在n == 3
的情况下返回。
您在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)
。因此,我们的最终计数将是:所有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
您在n = 3
的递归中的基本情况是错误的。对于n = 3
,正确答案应该是4
,但是您将返回3
。我建议您通过使用以下观察来简化基本情况: