【NK三】 跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

输入： 2
返回值： 2
说明： 青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2

以下整理为参考NK大神解析。

当n等于1的时候，只需要跳一次即可，只有一种跳法，记f(1)=1
当n等于2的时候，可以先跳一级再跳一级，或者直接跳二级，共有2种跳法，记f(2)=2
当n等于3的时候，他可以从一级台阶上跳两步上来，也可以从二级台阶上跳一步上来，所以总共有f(3)=f(2)+f(1)；
同理当等于n的时候，总共有f(n)=f(n-1)+f(n-2)(这里n>2)种跳法。
所以如果我们求上到n阶有多少种，代码很简单，直接递归就行。

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

这种当n比较大的时候会超时，所以不推荐，但如果还想使用递归我们可以改为尾递归的方式，我们来看下代码。

尾递归：如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。

public static int JumpFloor(int n) {
    return Fibonacci(n, 1, 1);
}
 
public static int Fibonacci(int n, int a, int b) {
    if (n <= 1)
        return b;
    return Fibonacci(n - 1, b, a + b);
}

但递归由于重复计算，导致效率很差，所以我们要把他给为非递归的。

public int JumpFloor(int n) {
    if (n <= 1)
        return 1;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

我们看到上面的数组当前值是依赖他前面两个值的（前两个除外），我们只需要用两个临时变量即可，不需要申请一个数组。

public int JumpFloor(int n) {
    if (n <= 2)
        return n;
    int first = 1, second = 2, sum = 0;
    while (n-- > 2) {
        sum = first + second;
        first = second;
        second = sum;
    }
    return sum;
}

青蛙跳台阶相关问题，我们可以找到他的递推公式是

这个公式其实就是斐波那契公式，1,1,2,3,5,8,13……，
但我们这道题的前几项是1,2,3,5,8……明显比那公式少了一项，所以这里计算第n项的指数应该是n+1。

public static int JumpFloor(int n) {
    double sqrt = Math.sqrt(5);
    return (int) ((Math.pow((1 + sqrt) / 2, n + 1) - Math.pow((1 - sqrt) / 2, n + 1)) / sqrt);
}