LeetCode 509：斐波那契数

链接
题目：

方法一：递归+备忘录（重叠子问题）

动态规划问题一般形式就是求最值；
因为要求最值，所以动态规划的核心问题是穷举；

需要掌握递归思维，只有列出正确的「状态转移方程」，才能正确地穷举；
而且需要判断算法问题是否具备「最优子结构」，是否能够通过⼦问题的最值得到原问题的最值；
另外，动态规划问题存在「重叠子问题」，如果暴⼒穷举的话效率会很低，所以需要使用「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。

状态转移方程、最优子结构、重叠子问题就是动态规划三要素；

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。

如果代码为：

class Solution {
    public int fib(int n) {
        //终止条件
        if(n==0 || n==1){
            return n;
            }
        return fib(n-1)+fib(n-2);
    }
}

则会有重复计算————重叠子问题

假设n=20：

20以下的每个节点都被计算了两次！
每个节点的时间复杂度为O(1) ，而节点数为O(2^n)，所以时间复杂度为O(1) x O(2^n) =O(2^n)，效率低；

dp定义：输入n，返回n的斐波那契数之和；
dp函数的参数n就是状态；
使用备忘录数组来解决重叠子问题：

返回值 (回溯) 就是要计算的值！**

class Solution {
    int[] memo;
    public int fib(int n) {
        memo=new int[n+1]; 
        Arrays.fill(memo,-111);//初始化memo以免弄混
        return dp(n);
    }
    int dp(int n){ // dp参数n 是状态
        // base case
        if(n==1 || n==0){
            return n;
        }
        // 重叠子问题
        if(memo[n]!=-111){
            return memo[n];
        }
        // 状态转移方程   回溯
        memo[n]=dp(n-1)+dp(n-2);
        return memo[n]; // dp返回值为所求的和
    }
}

或者用HashMap来作为备忘录，n为Key，n的计算结果为Value：

class Solution {
    HashMap<Integer,Integer> memo=new HashMap<>();
    public int fib(int n) {
        return check(n);
    }

    int check(int n){
        if(n==0 || n==1){
            return n;
        }
        if(memo.containsKey(n)){ // 已计算过, 避免重叠子问题
            return memo.get(n);
        }
        memo.put( n, check(n-1)+check(n-2) );
        return memo.get(n);
    }
}

带「备忘录」的递归算法，把⼀棵存在巨量冗余的递归树通过「剪枝」，改造成了⼀幅不存在冗余的递归图，极⼤减少了⼦问题（即递归图中节点）的个数；

以上解法是「自顶向下」进⾏「递归」求解，我们更常⻅的动态规划代码是「自底向上」进⾏「递推」求解。

啥叫「自顶向下」？注意我们刚才画的递归树（或者说图），是从上向下延伸，都是从⼀个规模较⼤的原问题⽐如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 这两个 base case，然后逐层返回答案，这就叫「⾃顶向下」。

啥叫「自底向上」？反过来，直接从最底下、最简单、问题规模最⼩、已知结果的 f(1) 和 f(2)（base case）开始往上推，直到推到想要的答案 f(20)。这就是「递推」的思路，这也是动态规划⼀般都脱离了递归，⽽是由循环迭代完成计算的原因。

方法二：递推迭代 + DP Table

引出「状态转移方程」这个名词，实际上就是描述问题结构的数学形式：

f(n) 的函数参数会不断变化，所以你把参数 n 想做⼀个状态，这个状态 n 是由状态 n – 1 和状态 n – 2转移（相加）⽽来，这就叫状态转移
动态规划问题最困难的就是写出这个状态转移方程；
只要写出暴力解，优化方法无非是用备忘录或者 DP table

利用DP table数组自底向上递推：

class Solution {
    public int fib(int n) {
        if(n==0){
            return 0;
        }
        int[] dp=new int[n+1];
        //base case
        dp[0]=0;
        dp[1]=1;

        // 自底向上递推
        for(int i=2;i<=n;i++){ // 遍历共2-n种状态
            dp[i]=dp[i-1]+dp[i-2]; // 状态转移 , 索引i/元素 是状态
        }
        return dp[n];
    }
}