一尘不染

计算采取1、2或3步后n步的爬升方式

algorithm

在书中,我遇到以下问题:

给定N阶楼梯,如果一次使用1、2或3阶,则可以爬多少条路?

以下是本书给出的代码:

 int countWays(int n){

    if(n<0)
        return 0;

    if(n == 0)
        return 1;

    else return countWays(n-1) + countWays(n-2) + countWays(n-3);
  }

在理解此代码时,我有以下担忧:

  1. 我不明白为什么要为n = 0返回1。如果有0步,那么显然我们不必爬任何步,应该返回0。

  2. 对于n = 3,函数返回4,但我只能看到3种情况,即(1,1,1),(1,2),(3)。


阅读 202

收藏
2020-07-28

共1个答案

一尘不染

我不明白为什么要为n = 0返回1。如果有0步,那么显然我们不必爬任何步,应该返回0。

当没有台阶时,您只是不爬而经过,这是唯一的一种方法。正如评论之一所指出的那样,它可以表示为()

对于n = 3,函数返回4,但我只能看到3种情况,即(1,1,1),(1,2),(3)。

实际上有4种情况:(1,1,1),(1,2),(2,1),(3)。

2020-07-28