DP求解斐波那契数列、青蛙跳台阶

1. 斐波那契数列

题目描述：写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。LeetCode链接

1. 递归求解

求解斐波那契数列相信之前大多数人会都使用递归来求解，如下所示

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

但是我们如果将递归展开，将会发现，递归求解中做了很多重复的工作，如下所示：我们如果要递归求解5，那么将会有很多重复的计算(下图中颜色相同的节点)，那么我们该怎么优化呢？

2. 记忆化递归法

? 最好的办法就是，在递归法的基础上，建立一个数组，用于存储fib(0) 至 fib(n)的计算结果，如果遇到相同的数字就可以不必计算，直接从数组取用，避免了重复的递归计算。

代码如下：

 public static int fibArray(int n)
    {
        int[] array = new int[n + 1];
        array[0] = 0;
        array[1] = 1;
        return fib(n, array);
    }

    private static int fib(int n, int[] array)
    {
        if (n <= 1)
        {
            return n;
        }
        if (array[n] != 0)//如果当前值不为0，说明已经计算过，重复递归直接返回
        {
            return array[n];
        }
        //如果当前值没被计算过，则递归计算
        return array[n] = fib(n - 1, array) + fib(n - 2, array);
    }

3. 动态规划

但是记忆化递归需要使用O(N)的额外空间,所以我们继续分析，进行优化

由于 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 我们发现，第N项只与第N-1项和第N-2项有关，所以我们只需要三个变量a,b,temp，使用辅助变量temp使a，b两个数字交替前进，这样的话空间复杂度将会减少到O(1)；

代码如下所示

public static int fib(int n)
{
    if (n <= 1)
    {
        return n;
    }
    int a = 0, b = 1, temp= a + b;
    for (int i = 2; i < n; i++)
    {
        a = b;
        b = temp;
        temp = a + b;
    }
    return temp;
}

4. 大数越界问题

随着 n的增大, fib(n) 会可能会超过int甚至是long的取值范围，导致最终的返回值错，所以我们还需要继续优化

求余运算规则：设正整数 x, y, p，求余符号为⊙ ，则有 (x + y)⊙ p =(x⊙p+y⊙p)⊙p 。

举个例子验证一下：3⊙2 = (2+1)⊙2 = 2⊙2+1⊙2 = 1+0 = 1

根据上面这个规则，我们可以推出：fib**(n)⊙p=[fib(n-1)⊙p + fib(n-2)**]⊙p,从而在计算中循环计算temp = (a + b) ⊙1000000007即可

如下所示：

public static int fib(int n)
{
    if (n <= 1)
    {
        return n;
    }
    int a = 0, b = 1, temp= a + b;
    for (int i = 2; i < n; i++)
    {
        a = b;
        b = temp;
        temp = (a + b) % 1000000007;
    }
    return temp;
}

2. 青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。LeetCode链接

分析：由于青蛙一次只有两种选择，跳上1级台阶和可以跳上2级台阶，那么假设现在有n级台阶，共有f(n)种跳法。那么在最后一步只有两种情况：

剩余1级台阶，那说明之前跳了n-1级，那么之前应该为f(n-1)种跳法。
剩余2级台阶，那说明之前跳了n-2级，那么之前应该为f(n-2)种跳法。

初始情况下

f(0) = 1，没有台阶的话原地跳

f(1) = 1 只有一个台阶的时候，只能跳 1 级

f(2) = 2 有两个台阶的时候，可以选择连续跳两次一次跳一级，也可以一次跳两级

综上，f(n) = f(n-1) + f(n-2)

分析后我们发现，这个和斐波那契数列几乎一样，只是初始值f(0)不同(斐波那契数列为0，青蛙跳台阶为1)，所以我们直接使用动态规划法，代码如下

public static int numWays(int n)
{
    //初始值：如果0级或者1级台阶有1种跳法
    if (n <= 1)
    {
        return 1;
    }
    int a = 1, b = 1, temp = a + b;
    //循环前进
    for (int i = 2; i < n; i++)
    {
        a = b;
        b = temp;
        temp = (a + b) % 1000000007;//取模
    }
    return temp;
}