基本情况背后的直觉，用于计算步数 [英] Intuition behind the base case for counting the number of steps

问题描述

我用一些在线帮助编写了以下解决方案的代码.目的基本上是找到一个人可以攀登n阶梯的方式的数量，如果他在每一步都可以攀登1或2阶梯的话.

I coded the following solution with some online help. The aim is basically to find the number of ways in which a person can climb a ladder of n steps, if at each step he can climb 1 or 2 steps.

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，我不会得到正确的答案.

While I am more or less aware about what exactly I am doing, I fail to understand the intuition behind returning 1 if the number of steps to be climbed is 0. Since we can take strides of length either 1 or 2, if the total number of steps to be climbed is 0, then shouldn't we return just a 0 (since no steps of length 1 or 2 can be taken)? Unfortunately, I don't get the correct answer if I return 0.

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

Could someone please explain what exactly is going on and the intuition behind returning 1 (instead of a 0)?

推荐答案

不是从可以采取多种方法到达顶部的方式来思考，而是从可以实现的方式中来思考.当您还有n个台阶要爬时，它会在顶部.如果n == 0，您有一种到达顶部的方法:留在原处.这就是直觉.

Instead of thinking about it in terms of how many different ways you can take steps to the top, think of it in terms of how many ways you can get to the top when you have n steps left to climb. If n == 0 you have one way to get to the top: stay where you are. That's the intuition.

实际原因是，如果没有对n == 0的定义，您将需要另外两个基本案例，即n == 1和n == 2才能为所有n > 0获得正确的答案.然后，您可以自由思考n == 0的正确答案应该是什么.

The practical reason is that without that definition for n == 0, you'd need two more base cases, for n == 1 and n == 2 to get the right answer for all n > 0. And then you would be free to puzzle over what the right answer should be for 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给出正确的答案.

Per request, here's why you'd need additional base cases if climbStairs(0) was 0. (Well, either you need additional base cases or you need to alter your recursion formula.) Whenever n is not a base case, climbStairs(n) is defined in terms of climbStairs(n-1) and climbStairs(n-2). If you define the n == 0 case as being 0, then, as you noticed, you don't get the right answer for n == 1 or n == 2. Therefore you'd have to define those as additional base cases. (Just fixing the n == 1 still wouldn't give the right answer for n == 2.) Once those additional base cases are established, the recursion formula will continue to give the correct answer for all n > 2.

这篇关于基本情况背后的直觉，用于计算步数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！