NC65：斐波那契数列/LeetCode：509.斐波那契数

分析

代码实现

public class Solution {
    public int Fibonacci(int n) {
        if(n == 0 || n == 1){
            return n;
        }
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
}

时间复杂度：

空间复杂度：

（2）动态规划（优化递归）

分析

• 通过上图会发现，方法一中使用递归会存在很多重复计算，因此为了改进，可以把使用数组将计算过的保存下来。
• 如果想让空间继续优化，那就用动态规划，优化掉递归栈空间，方法一是从上往下递归的然后再从下往上回溯的，在最后的回溯过程中来合并子树从而求得答案。
• 而使用动态规划，不用递归的过程，直接从子树求得答案，过程是从下往上。
  

代码实现1

public class Solution {
    public int Fibonacci(int n) {
        int ans[] = new int[40];//因为此题n≤39，所以直接设置数组大小为40
        ans[0] = 0;
        ans[1] = 1;
        for(int i=2; i<=n; i++){//从第二项开始计算到第n项，用数组进行保存
            ans[i] = ans[i-1] + ans[i-2];
        }
        return ans[n];
    }
}

代码实现2

根据输入的n确定数组的大小，n小于等于1就直接确定数组的值，大于1就从第三项开始计算到第n项，用数组进行保存

class Solution {
    public int fib(int n) {
        int[] dp = new int[n+1];
        if(n == 0){
            dp[0] = 0;
        }else if(n == 1){
            dp[0] = 0;
            dp[1] = 1;
        }else{
            dp[0] = 0;
            dp[1] = 1;
            for(int i = 2; i <= n; i++){
                dp[i] = dp[i - 1] + dp[i - 2];
            }
        }
        return dp[n];
    }
}

时间复杂度：
空间复杂度：

（3）动态规划（优化存储）

存储第n-2项的值，存储第n-1项的值，存储第n项的值，

public class Solution {
    public int Fibonacci(int n) {
        if(n <= 0){
            return 0;
        }
        if( n == 1){
            return 1;
        }
        int n1 = 0;
        int n2 = 1;
        int n3 = 0;
        for(int i = 2; i <= n; i++){
            n3 = n1 + n2; //根据前两项计算当前值
            n1 = n2;//n1，n2继续表示下一项的值
            n2 = n3;
        }
        return n3;
    }
}

n3 = n1 + n2;
n1 = n2;
n2 = n3;
//可使用两个参数实现优化
n2 = n1 + n2; //这里n2相当于获得了n3的值
n1 = n2 - n1; //n1获得了n2的值

public class Solution {
    public int jumpFloor(int target) {
        if(target <= 0){
            return 0;
        }
        if( target < 4){ //数列为0，1，2，3，5，8，13...
            return target;
        }
        int n1 = 2;
        int n2 = 3;
        for(int i = 4; i <= target; i++){//这里需要从第四项开始
            n2 = n1 + n2;
            n1 = n2 - n1;
        }
        return n2;
    }
}