递归-爬n层楼有多少种选择

Question

好吧，我有 "spiderman" 爬上了 n 层楼。如果他知道每次爬一层或两层，他有多少种选择可以到达第n层。

这是我目前所做的：（没有数组，没有 For 循环，保持简单）

public static int spiderman(int n,int i,int sum){
    if ( n == 0 )    return 0;
    if ( n < i) return 0;
    if ( n == i) return 1;
    sum += i;
    return spiderman(n,i + 1,sum) + spiderman(n,i + 2,sum);
}


  public static void main( String [] args ){
        System.out.println(spiderman(4,0,0)); //Should return 5
    }

输出：spiderman(4) returns 5. --已解决！

Answer 1

我觉得你的if ( n > i) return 0;应该是if ( n < i) return 0;，把符号反了。

此外，您 sum 变量似乎没有必要。它什么都不做，对你的函数结果没有影响

奖金：

你要回答的问题其实和斐波那契数列类似。这意味着您将看到以下模式：蜘蛛侠(n, 0, 0) == 蜘蛛侠(n - 1, 0, 0) + 蜘蛛侠(n - 2, 0, 0)。因为到达一层的方法数等于他可以到达下面楼层的方法数+下面2层，因为那些是他可以到达目标的楼层。

因此这是您问题的替代解决方案

public static int spiderman(int n){
    if (n < 3) return n;
    return spiderman(n - 1) + spiderman(n -2);
}

递归-爬n层楼有多少种选择

Recursion - how many options to climb the building with n floors

java

recursion