数据结构与算法

动态规划

Posted by lily on April 7, 2023

动态规划是什么？

定义

数组定义 在我的理解来看，动态规划的定义强调的是当下此时的状态是由前一时刻的状态推导而来的，它不是由搜索所有的前置状态而去匹配适合的上一个状态（那是深搜/广搜），而是强调这一刻与上一刻的逻辑依赖关系。 前置状态选择 这一刻动规数组表达的是什么，取决于我们对它的自定义。 上一刻是什么，该如何选择，到底是由什么推导而得到的此刻的状态？ 我看很多题目基本上都会将dp[i-1]这样的-1作为上一刻状态的表达，那么如果这个i是字符的长度，就代表上一刻就是i的前一个字符，这样就仅仅只需要讨论当两个字符串长度只差1时的差异关系，通过分类讨论或者逻辑推导，下一步就很方便的可以把状态转移方程写出来。 状态转移方程的推导

类型一：背包问题

01背包问题和完全背包问题都是经典的动态规划问题，主要用于解决资源分配和优化问题。

01背包

在01背包问题中，有一个背包，最大承重为W，和n个物品。每个物品都有一个重量和一个价值。每个物品只能选择放入背包或不放入（即“0-1”），不能分割。目标是选择物品，使得在不超过背包承重的情况下，背包中的物品总价值最大。

问题描述：

  • 输入：物品的重量数组weights、价值数组values和背包的最大承重W。
  • 输出：最大价值。

494. 目标和

中等，题目描述 :::tips 给你一个整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个 表达式 ：

  • 例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 ::: 解题思路 代码

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        // 能够得到target的目标和
        int sum = 0, left = 0;
        for(int k:nums){
            sum += k;
        }        
        if ((sum+target)%2 != 0) return 0;
        if (Math.abs(target)>sum) return 0;
        left = (sum+target)/2;
        // 构造一维dp数组
        int[] dp = new int[left+1];
        dp[0] = 1;
        for (int i=0;i<nums.length;i++){
            for(int j=left;j>=nums[i];j--) {
                dp[j] += dp[j - nums[i]];
            }  
        }
        return dp[left];
    }
}

完全背包

完全背包问题与01背包问题类似，但每个物品可以选择放入背包多次。也就是说，对于每个物品，可以选择放入0个、1个、2个……直到超过背包的承重为止。目标同样是使得背包中的物品总价值最大。

问题描述：

  • 输入：物品的重量数组weights、价值数组values和背包的最大承重W。
  • 输出：最大价值。

例题

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。 你可以认为每种硬币的数量是无限的。 示例 1： 输入：coins = [1, 2, 5], amount = 11 输出：3
解释：11 = 5 + 5 + 1

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = Integer.MAX_VALUE;
        // dp[i] 表示 总金额为i时所需要的最小硬币个数
        int[] dp = new int[amount+1];
        for (int i=1;i<=amount;i++){
            dp[i] = max;
        }
        // 不含顺序，先遍历物品, 当物品固定时背包扩大容量
        for (int i=0;i<coins.length;i++){
            // 遍历背包, 完全背包，正序遍历
            for (int j=coins[i];j<=amount;j++){
                if (dp[j-coins[i]] != max) 
                // 只有该位置被初始化过才能选择，
                // 否则会出现整数溢出 max+1 --> 变为负数，成为整个数组的最小值
                // 选择当前硬币，或不选择当前硬币，都能满足大小为j的背包
                    dp[j] = Math.min(dp[j-coins[i]]+1, dp[j]);
            }
        }
        return dp[amount]!=max ? dp[amount]:-1;

    }
}

279. 完全平方数

中等 输入：n = 12 输出：3 解释：12 = 4 + 4 + 4 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。 示例 1： :::tips 输入：n = 12 输出：3 解释：12 = 4 + 4 + 4 :::

class Solution {
    public int numSquares(int n) {
        if (n==1) return 1;
        int max = Integer.MAX_VALUE;
        int[] dp = new int[n+1];
        // 初始化dp，使得大于零的最小值能被赋值
        // dp[1]可由dp[0]推出（dp[1-1]），所以dp[0]一定要可选，保留dp0初始为0
        for (int k=1;k<dp.length;k++){
            dp[k] = max;
        }
        // 遍历物品，每个物品对应不同大小的背包
        for (int i=1;i<=n/2;i++){
            // 物品价值
            int value = i*i;
            // 遍历背包
            // 背包大小能装下物品才开始遍历，装不下物品则dp[j]取上层的结果
            for (int j=value;j<=n;j++){
                if (dp[j-value] != max)
                    dp[j] = Math.min(dp[j-value]+1, dp[j]);
            }
        }
        return dp[n];
    }
}

多重背包

多重背包问题是指每种物品可以选择多个，但每种物品的数量是有限制的。换句话说，你可以选择同一种物品多次，但不能超过其数量限制。 例子：
假设你在一个商店购物，商店里有以下商品：

  • 商品A（重2kg，价值30元），最多可以购买3个
  • 商品B（重3kg，价值50元），最多可以购买2个
  • 商品C（重1kg，价值10元），没有数量限制

在这个例子中，你可以选择多个商品，但每种商品的数量是有限制的。目标是最大化总价值，同时不超过背包的承重限制。

  • 多重背包：每种物品可以选择多个，但数量有限制。

例题

2585. 获得分数的方法数

2585. 获得分数的方法数 先遍历背包重量再遍历物品个数，因为同类型题目无法区分，且可以选择多个同类型题目 定义 f[i][j] 表示用前 i 种题目恰好组成 j 分的方案数。 对于第 i 种题目，枚举做 k 道题目，则子问题为「前 i−1 种题目恰好组成 j−k⋅marks i分的方案数」，因此有

f[i][j]= (k=0)∑​f[i−1][j−k⋅marksi] 注意 k 不能超过 count i ，且 j−k⋅marks i ≥0。

二维数组

class Solution {

    // 对结果取余

    private static final int MOD = (int) 1e9+7;

    public int waysToReachTarget(int target, int[][] types) {

        // 二维数组

        int n = types.length;

        // 代表前i种题目可以获取到j分数时的方法数

        int[][] dp = new int[n+1][target+1];

        // Arrays.fill(dp[0], 0);

        // 第-1种题目拿0分有一种方法（不选）

        dp[0][0] = 1;

        for (int i=0;i<n;i++){

            int count = types[i][0], marks = types[i][1];

            // 背包重量要从0开始计算，当前一分都不拿时的方案数

            for (int j=0;j<=target;j++){

                // 限制选择数量

                for (int k=0;k<=count && k<=j/marks;k++){

                    // 由前置状态推得：由前一种状态背包刚好空余j-k*marks重量时推得，若空余质量为0则表示不选当前题目

                    // 前i-1种题目恰好组成j-k*marks的方案数,不选时k=0

                    // 所有前置状态之和（不论选择多少道题取得的方案数之和）
                    dp[i+1][j] += dp[i][j-k*marks];
                    dp[i+1][j] %= MOD;
                }
            }
        }
        return dp[n][target];
    }
}

一维数组

class Solution {

    private static final int MOD = (int) 1e9+7;

    public int waysToReachTarget(int target, int[][] types) {

        // 一维数组

        int n = types.length;

        int[] dp = new int[target+1];

        dp[0] = 1;

        for (int[] t:types){

            int count=t[0], marks=t[1];

            for (int j=target;j>=0;j--){

                // 倒叙遍历k=0时j-k*marks=j，dp[j]已经被正确赋值

                // 含义：当前题型不选那么当前分数x的总个数就是选择前i道题型的总方案数，不需要再重新计算相加了

                for (int k=1;k<=count && k<=j/marks;k++){

                    dp[j] = (dp[j]+dp[j-k*marks])%MOD;

                }

            }

        }

        return dp[target];

    }

}

分组背包

先在同组中枚举，再枚举背包重量 分组背包问题是指将物品分为若干组，每组中只能选择一个物品。换句话说，物品之间是相互排斥的，不能同时选择同一组中的多个物品。

例子：
假设你要参加一个活动，需要选择不同类型的装备。装备分为三组：

  • 第一组：帐篷（重5kg，价值100元）、睡袋（重2kg，价值50元）
  • 第二组：炉具（重3kg，价值80元）、炊具（重1kg，价值30元）
  • 第三组：食物（重4kg，价值60元）、水（重1kg，价值20元）

在这个例子中，你只能从每组中选择一个装备，目标是最大化总价值，同时不超过背包的承重限制。

有顺序的背包

放入背包中的元素的顺序是有意义的，而不是简单的满足背包重量即可

例题

139. 单词拆分

139. 单词拆分 如果把本题看作一个有顺序的背包问题，那么放入背包中的元素顺序必须按照单词s的顺序进行放入，并且只需要找到一种放入顺序即可（可以按顺序放入返回true）

带顺序的背包解法 ` 用时: 50 m 58 s ]` 有顺序的背包，线性dp，依赖前置状态，先遍历背包再遍历物品

class Solution {

    public boolean wordBreak(String s, List<String> wordDict) {

        // 背包

        int n = s.length();

        // dp[i]表示0-i（闭区间）的字串能否被拼接

        boolean[] dp = new boolean[n+1];

        // s中没有字符时一定可以拼接

        // 依赖前置状态：当字典中的字符恰好等于当前遍历的字符（i==word.length()）,剩余字符长度为0

        dp[0] = true;

        // 先遍历背包,在背包中查询是否存在某个单词

        for (int i=1;i<=n;i++){

            // 遍历物品(检查是否能被字典中的字符拼接，所以以物品为单位)

            for (int j=0;j<wordDict.size();j++){

                String word = wordDict.get(j);

                if (i<word.length()) continue;

                // 直接存在0-i整个单词或是0-j部分为true且j+1-i部分可以由字符拼接
                dp[i] = dp[i] || (dp[i-word.length()] && s.startsWith(word, i-word.length()));
            }
        }
        return dp[n];
    }
}

知识点：

在 Java 中，s.startsWith(sub, len) 方法用于检查字符串 s 是否从指定的索引 len 开始以子字符串 sub 开头。
String s = "Hello, world!";
boolean result = s.startsWith("world", 7); // 返回 true
boolean result2 = s.startsWith("Hello", 0); // 返回 true
boolean result3 = s.startsWith("world", 0); // 返回 false

序列dp解法 需要注意由于截取0-i子串时，函数区间为左开右闭，所以遍历获取子串的边界条件要注意 以及判断一旦dp[i]被赋值为true之后就不再进行分割子串

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 序列dp
        HashSet<String> wd = new HashSet<>();
        for (String word:wordDict) wd.add(word);
        int n = s.length();
        // 下标后移1

        boolean[] dp = new boolean[n+1];

        // dp需要依赖前置状态，由于要考虑背包第一个容量时的依赖关系，所以需要初始化前置状态

        dp[0] = true;

        for (int i=1;i<=n;i++){

            // 如果dp[i] 曾经找到了合适的word被赋值为true那么就不继续寻找了

            // j从1开始遍历，整体向右移1，但下述使用j时同时-1往左移

            for (int j=1;j<=i && !dp[i];j++){

                String sub = s.substring(j-1,i);

                // 从j-(i-1)的字符已经存在，验证0-(j-1)的字符是否存在

                if (wd.contains(sub)) dp[i] = dp[j-1];
            }
        }
        return dp[n];
    }
}

序列[dp]与线性[dp]

总结

  • 01背包问题：每个物品只能选择一次。
  • 完全背包问题：每个物品可以选择多次。
  • 分组背包：每组只能选择一个物品，物品之间相互排斥。
  • 多重背包：每种物品可以选择多个，但数量有限制。

这两种问题都可以通过动态规划的方法来解决，通常使用二维数组或一维数组来存储中间结果，或者选择递归调用来代替二维数组空间的使用。 背包问题解决的是选择结果是与选择顺序无关的题目

变形

  • 至多/至少/恰好问题

经典线性动态规划

  1. 动归数组的含义 tips
    • 一维dp数组，dp[i]的值可由查询数组之前已经赋过的值确定，类似逻辑关系的地推出整个数组，只需查询数组的值即可获得满足当前条件的结果, 即明确生成的dp数组可以为推导出结果而服务
    • 动态规划数组，是一个可由前一个递推结果推出后续值的数组
  2. 如何创建动归数组
    1. 确定 i 的含义–>数组索引值代表含义
    2. 确定dp[i]代表什么

由题目逻辑推导出dp[i]公式 例如：dp[i] = dp[i-1] + dp[i-2]; 递推公式具有明确的实际含义

  1. 确定动归数组的length， 循环索引值 i 设计等问题

    例题

    打家劫舍一

    class Solution {
 public int rob(int[] nums) {
     if (nums.length == 1) return nums[0];
     //dp[i] 表示偷窃第i家累计的总金额 
     int[] dp = new int[nums.length];
     // 确定依赖关系：dp[i] = max(偷i， 不偷i)， 不偷i，dp[i]能取dpi-1；偷i，推出已偷i-2，dp[i]取dpi-2 + 当前i的价值
     // 初始化dp数组：第1家只能偷，第2家不一定能偷
     dp[0] = nums[0];
     dp[1] = Math.max(nums[0], nums[1]);
     for (int i=2;i<nums.length;i++){
         dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
     }
     return dp[dp.length-1];
 }
}

多维动态规划

一维动态规划通常只处理一个状态变量（如数组），而多维动态规划处理多个状态变量（如矩阵）。 且题目中会规定状态转移的方向 说明：每次只能向下或者向右移动一步。

例题

64最小路径和

64. 最小路径和 dp定义好后状态初始化比较简单

class Solution {

    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        // dp[i][j]表示到达该点时路径上的最小和
        int[][] dp = new int[m][n];
        // 初始化
        dp[0][0] = grid[0][0];
        for (int i=1;i<m;i++) dp[i][0] += dp[i-1][0]+grid[i][0];
        for (int j=1;j<n;j++) dp[0][j] += dp[0][j-1]+grid[0][j];
        // 每条路都是左或上来的
        for (int i=1;i<m;i++){
            for (int j=1;j<n;j++){
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}

62. 不同路径

62. 不同路径

class Solution {

    public int uniquePaths(int m, int n) {

        int[][] dp = new int[m][n];

        for (int i=0;i<m;i++){

            for (int j=0;j<n;j++){

                if (i==0 || j==0){

                    dp[i][j] = 1;

                }else {

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

                }

            }

        }

        return dp[m-1][n-1];

    }

}

5. 最长回文子串

5. 最长回文子串 三种解法

  1. 暴力解法
  2. 动态规划
  3. 中心扩散法（未完成）

暴力解法

  1. 遍历找到所有长度大于2的子串
    1. 遍历时若i在外层，j在内层，要控制子串长度j=i+1,那么i<n-1,因为当当i=n-1是，j=n 
      class Solution {
    public String longestPalindrome(String s) {
        // 暴力解法
        int n = s.length();
        if (n<=1) return s;
        // 枚举所有长度大于2子串，判断是否回文，保存最大回文长度 + 起始位置
        int maxLen = 1;
        int start = 0;
        // 优化，s.charAt(i)每次都会判断下标是否越界，增加时间
        char[] charArray = s.toCharArray();
        // i<n-1,控制子串最小长度为2，且j不越界（当i=n-1是，j=n）
        for (int i=0;i<n-1;i++){
            for (int j=i+1;j<n;j++){
                // 判断是否回文
                // 剪枝，长度没有大于最新长度不用调用函数
                if (j-i+1>maxLen && isPliandrome(charArray,i, j)){
                    maxLen = j-i+1;
                    start = i;
                }
            }
        }
        return s.substring(start, maxLen+start);
    }
    private boolean isPliandrome(char[] charArray, int begin, int end){
            while (begin<=end && charArray[begin] == charArray[end]){
                begin++;
                end--;
            }
        return begin>end;
    }
}

动态规划

动态规划遍历时要注意先初始化前置关系的dp数组。 对于dp[i+1][j-1]这种前置关系 如果先遍历后一个下标，那么当j=2时，i可以为0，1。由于此时j=1的下标已经全部被遍历过，所以dp[?][j-1]一定是被初始化过的状态。

即对于dp[i+1][j-1]这种关系，[i][j]当【小的下标的最大值都被遍历过之后，大的下标的最小值也会被填充过】（/？）。

在这个算法中，遍历的顺序会影响到动态规划表 dp 的填充方式。具体来说，先遍历 j 再遍历 i 和先遍历 i 再遍历 j，会导致不同的状态更新顺序，进而影响到最终结果。

class Solution {
    public String longestPalindrome(String s) {
        // 动态规划
        int n = s.length();
        // 转换
        char[] chars = s.toCharArray();
        // dp[i][j]表示闭区间i-j是否为回文串
        boolean[][] dp = new boolean[n][n];
        int max = 1;
        int start = 0;
        // 遍历二维数组，只使用和计算对角线上方的元素
        for (int j=1;j<n;j++){
            for (int i=0;i<n;i++){
                // 长度为1，是回文串
                if (j-i+1<2){
                    dp[i][j] = true;
                } else if (j-i+1<4){
                    // 当子串长度==2 或==3时，是否为回文串由s[i]==s[j]判断
                    dp[i][j] = (chars[i]==chars[j]);
                }else {
                    dp[i][j] = (chars[i]==chars[j]) && dp[i+1][j-1];
                }
                // 记录最大长度和起始下标
                if (dp[i][j] && j-i+1>max){
                    max = j-i+1;
                    start = i;
                }
                // System.out.println(i+", "+j+": "+start+", "+max);
            }
        }
        return s.substring(start, start+max);
    }
}

动规中遍历的顺序

需要先初始化前置关系的

例如题5. 最长回文子串 对于dp[i+1][j-1]这种前置关系 如果先遍历后一个下标，那么当j=2时，i可以为0，1。由于此时j=1的下标已经全部被遍历过，所以dp[?][j-1]一定是被初始化过的状态。

在这个算法中，遍历的顺序会影响到动态规划表 dp 的填充方式。具体来说，先遍历 j 再遍历 i 和先遍历 i 再遍历 j，会导致不同的状态更新顺序，进而影响到最终结果。

  1. 先遍历 j 再遍历 i：
    • 这种方式会从较小的 j 开始，逐渐增大 j，对于每个 j，会遍历所有可能的 i。在这种情况下，较小的子串会在较大的子串之前被计算，这样可以确保在计算 dp[i][j] 时，dp[i+1][j-1] 已经被计算过。
  2. 先遍历 i 再遍历 j（j=i+1 开始）：
    • 这种方式会从每个 i 开始，逐渐增大 j。在这种情况下，j 会从 i+1 开始，意味着对于每个 i，只会计算比 i 大的子串。这可能导致在计算某些 dp[i][j] 时，所需的 dp[i+1][j-1] 还没有被计算。
实际例子1

假设有一个字符串 s = "aba"，对应的字符数组 chars = ['a', 'b', 'a']。

  • 先遍历 j 再遍历 i：
    • 当 j=2 时，i 可以是 0 或 1。
      • 对于 i=0，计算 dp[0][2]，需要检查 chars[0] == chars[2]（即 a == a），并且 dp[1][1] 已经计算过（为 true），所以 dp[0][2] 为 true。
      • 对于 i=1，计算 dp[1][2]，需要检查 chars[1] == chars[2]（即 b == a），所以 dp[1][2] 为 false。
  • 先遍历 i 再遍历 j（j=i+1 开始）：
    • 当 i=0 时，j 从 1 开始：
      • 对于 j=1，计算 dp[0][1]（chars[0] == chars[1]，即 a == b），所以 dp[0][1] 为 false。
      • 对于 j=2，计算 dp[0][2]，此时 dp[1][1] 还未被计算，所以可能会导致错误的结果。
    • 当 i=1 时，j=2，直接计算 dp[1][2]，结果为 false。

通过这个例子可以看出，遍历顺序会影响 dp 表的计算顺序，进而影响最终的回文串判断。正确的顺序确保了所需的状态已经被计算，有助于动态规划的有效性。

CATALOG
    FEATURED TAGS
    JAVASE JavaWEB Spring python基础 学习工具 数据结构与算法 爬虫学习 计算机网络 springBoot BugNotice springSecurity projectLearning SQL
    FRIENDS