algorithm - 计算走 1、2 或 3 步后爬 n 步的方法

Question

在一本书中我遇到了以下问题:

给定 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)。

Answer 1

I do not understand why 1 is being returned for n=0. If there are 0 steps then obviously we do not have to climb any and 0 should be returned.

当没有台阶时，你只能通过而不是攀登，这是唯一的一种方式。正如其中一条评论所指出的，它可以表示为 ()。

For n=3 function returns 4 but i can see only 3 cases i.e. (1,1,1), (1,2), (3).

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