动态规划

斐波那契数列的三种解法

直接暴力递归

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

时间复杂度的计算：

递归次数*每一次递归所消耗的时间

递归数的高度为n，节点数为2^n，每一次递归只有判断和加法操作，所以时间复杂度为2^n，从节点数的计算过程可以看出： 在递归过程中，节点的计算过程有很多重复的地方，比如图中标出的17和18节点，那该如何避免重复计算呢？

有两种方法：一种是在自顶向下递归过程中加备忘录，还有一种是自底向上，从0，1开始构建dp数组，求出dp数组的每一个数

自顶向下添加备忘录(核心逻辑，判断备忘录+添加备忘录)

public int fib(int n) {
    int[] dp=new int[n];
    return df(n,dp);
}
public int df(int n,int[] dp){
    if(n<=1){
        return n;
    }
    //判断备忘录，在右子树判断成功
    if(dp[n-1]>0){
        return dp[n-1];
    }
    //添加备忘录，在左子树dfs递归时添加
    dp[n-1]=df(n-1,dp)+df(n-2,dp);
    return dp[n-1];
}

执行流程如下

Step 1: df(4) 进场
   |-- 查表 dp[3]？空。
   |-- 准备计算：df(3) + df(2)
   |
   |--> Step 2: 调用 df(3)
         |-- 查表 dp[2]？空。
         |-- 准备计算：df(2) + df(1)
         |
         |--> Step 3: 调用 df(2)
               |-- 查表 dp[1]？空。
               |-- 准备计算：df(1) + df(0)
               |
               |--> Step 4: 调用 df(1)
               |     |-- n<=1，返回 1
               |
               |--> Step 5: 调用 df(0)
               |     |-- n<=1，返回 0
               |
               |-- 计算 dp[1] = 1 + 0 = 1
               |-- 【记录】 dp[1] (即 dp[n=2对应的位置]) = 1
               |-- 返回 1
         |
         |--> Step 6: 调用 df(1)
               |-- n<=1，返回 1
         |
         |-- 计算 dp[2] = 1 + 1 = 2
         |-- 【记录】 dp[2] (即 dp[n=3对应的位置]) = 2
         |-- 返回 2
   |
   |--> Step 7: 调用 df(2)  <-- 【关键点：这里不一样了！】
         |-- 查表 dp[1]？
         |-- **发现 dp[1] > 0 (之前Step 3算过了，是1)**
         |-- **直接返回 1 (剪枝，不再递归)**
   |
   |-- 计算 dp[3] = 2 + 1 = 3
   |-- 【记录】 dp[3] (即 dp[n=4对应的位置]) = 3
   |-- 返回 3

结果：3

左子树进行全部计算，备忘录在右子树生效

自底向上添加备忘录，使用for循环

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

最后直接返回数组中的值就行了