[笔记]动态规划

简单介绍

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的。这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。【动规是由前一个状态推导出来的，而贪心是局部直接选最优的】

所以贪心解决不了动态规划的问题

解题思路

1. 确定dp数组（dp table）以及下标的含义

2. 确定递推公式

3. dp数组如何初始化【根据第2步判断】

4. 确定遍历顺序

5. 举例推导dp数组

一维入门

【简单】509. 斐波那契数

509. 斐波那契数 - 力扣（LeetCode）

分析：当前状态由前两个状态推出，可以使用动规

五步走：

1. 确定dp数组（dp table）以及下标的含义：dp[i]表示第i个数字为多少

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

3. dp数组如何初始化

   1. 根据上一步进行初始化

   2. 注意题目也给了：dp[0] = 0,dp[1] = 1

4. 确定遍历顺序：dp[i] = dp[i-1] + dp[i-2]可知从前往后遍历

5. 举例推导dp数组

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

⭐优化：我们只在乎dp[i] 、dp[i-1]、dp[i-2]三个数字，而不需要记录整个序列

class Solution {
    public int fib(int n) {
        if (n <= 1)
            return n;
        int[] dp = new int[2];    // 数组大小改为2
        int temp = 0;
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {  // 更新dp
            sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = temp;
        }
        return sum;
    }
}

【简单】70. 爬楼梯

70. 爬楼梯 - 力扣（LeetCode）

分析：主要是由每次可以爬1/2层推出递归公式 ＋ 初始化从1开始

五步走：

1. 确定dp数组（dp table）以及下标的含义：dp[i]表示第i层楼梯有多少种到达方式

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

3. dp数组如何初始化

   1. 根据上一步进行初始化

   2. 注意题目也给了：dp[1] = 1,dp[2] = 2

4. 确定遍历顺序：dp[i] = dp[i-1] + dp[i-2]可知从前往后遍历

5. 举例推导dp数组

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

同样可以优化空间，方法同509

【简单】746. 使用最小花费爬楼梯

746. 使用最小花费爬楼梯 - 力扣（LeetCode）

分析：看起来涉及到两个维度：阶梯数＆体力，但是这两个维度是联系的（也就是阶梯数对应体力）

五步走：

1. 确定dp数组（dp table）以及下标的含义：dp[i]表示到达第i层花费的最小体力

2. 确定递推公式：dp[i] = min(dp[i-1] + cost[i-1] , dp[i-2] + cost[i-2])，也计算就是从第i-1层还是第i-2层跳到第i层花费体力小

3. dp数组如何初始化

   1. 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯：dp[0] = 0,dp[1] = 0

4. 确定遍历顺序：由递推公式可知从前往后遍历

5. 举例推导dp数组

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        // ❗【这个很重要】 dp含义:dp[i],i表示阶梯数，dp[i]表示花费的总体力
        // 【第二个要注意的就是第一级和第二级是不花费体力的，如果从这两级出发才用体力】
        int length = cost.length;
        if(length==1) return 0;
        if(length==2) return Math.min(cost[0],cost[1]);
        int[] dp = new int[length+1];
        dp[0] = 0;
        dp[1] = 0;
        for(int i=2;i<=length;i++){
            dp[i] = Math.min(dp[i-1] + cost[i-1] ,dp[i-2] + cost[i-2]);
        }
        return dp[length];
    }
}

同样可以优化空间，方法同509

二维入门

【中等】62.不同路径

62. 不同路径 - 力扣（LeetCode）

分析：当前点位置路径数 = 左侧位置路径数+上侧位置路径数

五步走：

1. 确定dp数组（dp table）以及下标的含义：dp[i] [j]表示到达(i,j)的路径有多少条

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

3. dp数组如何初始化

   1. dp[0] [0] = 0

   2. 第一行和第一列都是1

4. 确定遍历顺序：由递推公式可知从前往后遍历

5. 举例推导dp数组

    public int ( m, int n) {
        if(m==1 && n==1)  return 1;
       int[][] dp = new int[m][n];
            // dp[i][j] 表示达到[i,j]处的路径数
            // 初始化，第一行和第一列都初始化成1
            dp[0][0] = 0;
            for (int i = 1; i < m; i++) 
                dp[i][0] = 1; 
            
            for (int j = 1; 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];
    }
}

优化：状态压缩

// [优化]：关于对角线对称，本质上就是杨辉三角
// 根据 dp[i][j]=dp[i−1][j]+dp[i][j−1]可以发现，只需要用到上一行和当前行的数据，而不需要之前所有行的数据
// 所以我们用一维数组就可以解决，dp[j] 表示从左边到达当前位置的路径数，dp[j - 1] 表示从上面到达当前位置的路径数
class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        // 第一行
        for (int j = 0; j < n; j++)
            dp[j] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {

【中等】63. 不同路径 II

63. 不同路径 II - 力扣（LeetCode）

分析：总体思路同上，遇到障碍物把当前路径数设为0就好了

五步走：

1. 确定dp数组（dp table）以及下标的含义：dp[i] [j]表示到达(i,j)的路径有多少条

2. 确定递推公式：dp[i] [j] = dp[i] [j-1] +dp[i-1] [j]; if(obstacleGrid[i] [j] == 0) dp[i] [j] = 0

3. dp数组如何初始化

   1. dp[0] [0] = 0

   2. 第一行和第一列都是1

4. 确定遍历顺序：由递推公式可知从前往后遍历

5. 举例推导dp数组

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];

        // 如果在起点或终点出现了障碍，直接返回0
        if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1)
            return 0;
            dp[i][0] = 
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; 
            dp[0][j] = 1;

        for (int i = 1; i < m; 
            for (int j = 1; j < n; j
            // 碰到状态直接将状态设为0就可以了
                dp[i][j] = (obstacleGrid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0;
        return dp[m - 1][n - 1];
    }
}

优化：思路同62

顺带嘲笑一下脑子没转过弯来的自己

使用一维不要忘记初始化第一行!!!!!

【中等】 343. 整数拆分

343. 整数拆分 - 力扣（LeetCode）

分析：一开始会一直纠结到底是分成两个数还是几个数，我们统一分成两个数

dp[i]有两种得到方式：

1. 直接拆分：j * (i - j) 【真正意义上的拆分成两个数】

2. 继续拆分：j * dp[i - j] 【这个就相当于把i-j再进行拆分，也就包括了多个数的情况】

五步走：

1. 确定dp数组（dp table）以及下标的含义：dp[i] 表示i可以被拆分的最大乘积

2. 确定递推公式：

   1. dp[i] = max(dp[i] , max((i-j) * j , dp[i-j] * j))

   2. 两层max：里面的max是比较直接拆分和继续拆分的大小，外面的是把当前dp[i]和新的计算结果相比

3. dp数组如何初始化：dp[2] = 1，0和1没有意义

4. 确定遍历顺序：双层遍历

5. 举例推导dp数组

class Solution {
    public int integerBreak(int n) {
        // dp[i]表示n=i时的最大乘积
        int[] dp = new int[n + 1];
        // 递推公式 dp[i] = (i-j)*j【两个数】 / dp[i-j]*j【多个数】
        // 初始化：只用初始化dp[2]就行，0和1没有意义
        dp[2] = 1;
        // 遍历顺序：i从3遍历到n
        // j表示分成的两个数，从1遍历到i/2【为什么不到i，因为对称（意会一下】
        for (int i = 3; i <= n ; i++) {
            for (int j = 1; j <= i / 2; j++)
                // 还要再max一下，因为dp[i]时要不断把这个值和新的值进行比较更新
                dp[i] = Math.max(dp[i],Math.max((i-j)*j,dp[i-j]*j));
        }
        return dp[n];
    }
}

【中等】 96.不同的二叉搜索树

96. 不同的二叉搜索树 - 力扣（LeetCode）

分析：额有点数学题，难度可以算半个困难了【推导过程见代码随想录 (programmercarl.com)】

反正最后可以推出dp[i] += dp[j - 1] * dp[i - j]，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量

五步走：

1. 确定dp数组（dp table）以及下标的含义： 1到i为节点组成的二叉搜索树的个数为dp[i]

2. 确定递推公式：

   1. dp[i] += dp[j - 1] * dp[i - j];

   2. j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量

3. dp数组如何初始化：dp[0] = 1

4. 确定遍历顺序：遍历i里面每一个数作为头结点的状态，用j来遍历。

5. 举例推导dp数组

class Solution {
    public int numTrees(int n) {
        // 主要是数学推导？
        // 递推公式：f(i)=G(i−1)∗G(n−i)
        // 以i为根节点的二叉搜索树的数量等于以i-1的总数的二叉搜索树的数量乘以以n-1的二叉搜索树的数量。
        int[] dp = new int[n + 1];
        // 初始化0个节点和1个节点的情况
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                // 对于第i个节点，需要考虑1作为根节点直到i作为根节点的情况，所以需要累加
                // 一共i个节点，对于根节点j时,左子树的节点个数为j-1，右子树的节点个数为i-j
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}

背包问题

416.分割等和子集1

对于面试，只需要掌握到01背包和完全背包就够了

01 背包

题目：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

分析：

五步走：

1. 确定dp数组（dp table）以及下标的含义： 即dp[i] [j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

2. 确定递推公式：dp[i] [j] = max(dp[i - 1] [j], dp[i - 1] [j - weight[i]] + value[i]);

   1. 不放物品i：也就是dp[i - 1] [j]，即背包容量为j，里面不放物品i的最大价值，所以背包内的价值依然和前面相同。

   2. 放物品i：也就是dp[i - 1] [j - weight[i]] + value[i] 推出

      1. dp[i - 1] [j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值

      2. 那么dp[i - 1] [j - weight[i]] + value[i] ，就是背包放物品i得到的最大价值

3. dp数组如何初始化：

   1. 首先从dp[i] [j]的定义出发，如果背包容量j为0的话，即dp[i] [0]，无论是选取哪些物品，背包价值总和一定为0。

      

      动态规划-背包问题2
   2. 状态转移方程 dp[i] [j] = max(dp[i - 1] [j], dp[i - 1] [j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。

4. 确定遍历顺序：

   1. 先遍历物品还是先遍历背包重量呢？

5. 举例推导dp数组

打家劫舍

买卖股票

子序列