c++ - 计算步数的基本情况背后的直觉

Question

我使用一些在线帮助编写了以下解决方案。目标基本上是找出一个人可以爬上 n 阶梯的方法数，如果他在每一步都可以爬 1 或 2步骤。

class Solution {
public:
    int climbStairs(int n) {
        if(n<0)
            return 0;

        //what is the logic used for the following return?
        if(n==0)
            return 1;

        return climbStairs(n-1)+climbStairs(n-2);
    }
};

虽然我或多或少知道我到底在做什么，但如果要攀登的步数为 0，我无法理解返回 1 背后的直觉.由于我们可以采用 1 或 2 的步长，如果要攀爬的总步数是 0，那么我们不应该只返回一个 0(因为不能采用长度为 1 或 2 的步骤)？不幸的是，如果我返回 0，我得不到正确的答案。

有人可以解释一下到底发生了什么以及返回 1(而不是 0)背后的直觉吗？

Answer 1

与其考虑有多少种不同的方法可以到达顶部，不如考虑有多少种方法可以到达顶部，当您有 n 步时离开攀登。如果 n == 0，您只有一种方法可以登顶:留在原地。这就是直觉。

实际原因是，如果没有 n == 0 的定义，您还需要两个基本情况，n == 1 和 n == 2 以获得所有 n > 0 的正确答案。然后你就可以自由地思考 n == 0 的正确答案应该是什么。

根据请求，如果 climbStairs(0) 为 0，这就是为什么您需要额外的基本情况。(好吧，要么您需要额外的基本情况，要么您需要改变您的递归公式。)每当n 不是基本情况，climbStairs(n) 是根据 climbStairs(n-1) 和 climbStairs(n -2)。如果您将 n == 0 的情况定义为 0，那么，正如您所注意到的，您不会得到 n == 1 或 的正确答案n == 2。因此，您必须将这些定义为额外的基本案例。 (只是修复 n == 1 仍然不会为 n == 2 给出正确答案。)一旦建立了这些额外的基本情况，递归公式将继续为所有 n > 2 给出正确答案。