1

在书中，我遇到了以下问题：

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

4

3 回答 3

2

我不明白为什么 n=0 会返回 1。如果有 0 个台阶，那么显然我们不必爬任何台阶，应该返回 0。

当没有台阶时，您无需攀爬就可以通过，这是唯一且唯一的方法。正如其中一条评论所指出的，它可以表示为()。

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

实际上有4种情况：（1,1,1），（1,2），（2,1），（3）。

于 2013-03-10T02:46:26.037 回答
0

正如 Geobits 所说，爬 3 级楼梯有四种方法

(1,1,1),(1,2),(2,1),(3)

至于为什么它返回 1 when n==0，这是因为只要n==0这意味着你已经找到了 1 种爬楼梯的方法。

最后，如果您输入任何高数字，此算法将花费很长时间，如果您正在寻找一种动态编程方法，您应该创建一个n大小数组并将前三个条目初始化为1,2,4，然后遍历数组起始和索引 3，每次将索引设置为array[i-1] + array[i-2] + array[i-3]. 这将做最少的计算，但会使用大量的内存。

有一种更好的方法，您只使用 1x3 大小的数组，但我将把如何做到这一点留给用户作为练习。

于 2013-03-10T02:44:49.987 回答
0

我不明白为什么 n=0 会返回 1。如果有 0 个台阶，那么显然我们不必爬任何台阶，应该返回 0。

为了补充Terry的答案，问题的一般答案是tribonacci(n+2)序列。因此，对于n=0，即tribonacci(2)，值是 1。这只是楼梯问题的计算技巧，一个有效的方法。如需更彻底的调查，请参阅此答案。

你当然可以选择拒绝f(n=0) = 1。如果你这样做了，那么你可以只使用以下你会更舒服的基本情况值。所有n>3这些都将递归到这些基本案例。

  • f(n=1) = 1
  • f(n=2) = 2
  • f(n=3) = 4
于 2016-12-05T09:35:09.643 回答