java算法：力扣动态规划公式和例子，套这个就够了！

持续更新…
（跟着代码随想录总结的）

使用场景：只要数值无限依赖于前面的数值就可以套用这个公式

五步法

1. dp数组及下标的含义

2. 递推公式

3. dp数组如何初始化

4. 遍历顺序

5. 打印dp数组

经典举例：斐波那契数

斐波那契数是：一个数组得的某个数字等于前两个数字之和

dp[i]  dp[i][j]

1. dp[i]表示第i个斐波那契数的数值dp[i]

2. 递推公式：dp[i] = dp[i-1] +dp[i-2]

3. dp数组的初始化：0和1开始 所以dp[0] = 0; dp[1] = 1;

4. 确定遍历顺序：这个题由于求最后的n，依赖于之前的每个数，所以从前往后遍历。

5. 打印dp数组，在idea上验证我们写的代码没有问题

   public int fib(int n) {
           //由于下标为length-1，搜易想要求n位置的值数组长度必须为n+1
           int[] dp = new int[n+1];
           //无法用递推公式做出来的数值
           if (n == 0) {
               return 0;
           }
           if (n == 1) {
               return 1;
           }
           //初始值
           dp[0] = 0;
           dp[1] = 1;
           //遍历顺序+递推公式
           for (int i = 2; i <= n ; i++) {
               dp[i] = dp[i-1]+ dp[i-2];
               if (i == n){
                   dp[n] = dp[i];
               }
           }
           return dp[n];
   }
   

爬楼梯 leetcode70

规律总结：1阶 1种，2阶 2种， 3阶 3种，4阶 5种，总结出来就是第n阶的方法数等于(n-1)的方法数量+n+1的方法数量

1. 达到第i阶有dp[i]种方法 dp[i-2] dp[i-1]和斐波那契很像；但是换种方法 定义三个初始值记录前一个后一个

2. res= front + back;

3. 从前往后推

4. dp[1] = 1; dp[2] = 2; dp[3] = 3;

   class Solution {
       public int climbStairs(int n) {
           //定义初始值；递推公式遵循res等于前两个的值
           int front = 0;
           int back = 0;
           int res = 1;
           for (int i = 1; i <= n; i++) {
                front = back;//把back赋值给这个值
                back = res;//不断得把上一个结果res赋值给back
                res= front + back;
           }
           return res;
       }
   }
   

   使用最小花费爬楼梯 leecode746

1. dp[i] 为到达下标i得位置所需要的花费为dp[i]

2. 递推公式：求的是dp[i] 可以由dp[i-1]跳了一步得到所花费为dp[i-1]+cost[i-1]，或者dp[i-2]跳了两步得到，所花费为dp[i-2+cost[i-2]；将二者比较，选最小值

3. 初始化：dp[1]=0和dp[0]=0,因为后面的都基于这两个

4. 遍历顺序：从0往后遍历，后面依赖于前面

    int n = cost.length;
           int[] dp = new int[n + 1];
           dp[0] = dp[1] = 0;
           for (int i = 2; i <= n; i++) {
               dp[i] = Math.min(dp[i-1] +cost[i-1],dp[i-2]+cost[i-2]);
           }
           return dp[n];
   

不同路径 LeetCode62

1. dp[i][j]数组的含义:从（0，0）到终点（i，j）的含义

2. 递推公式：dp[i][j]只能由上或者下来推导出来，上的坐标值为dp[i-1]j,左的值为dp[i][j-1],所以dp[i][j] = dpdp[i-1][j]+dp[i][j-1]
   3.初始值dp[0][0] = 0; dp[1][0] = 1;dp[0][1] = 1;
   4.遍历顺序:由于最后的以来前面的，所以从前往后遍历

 public static int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        if (m == 0&&n == 0){
            return 0;
        }
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m ; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }