数据结构与算法

动态规划

Posted by lily on April 7, 2023

类型一：背包问题

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];
 }
}
CATALOG
    FEATURED TAGS
    JAVASE JavaWEB Spring python基础 学习工具 数据结构与算法 爬虫学习 计算机网络 springBoot BugNotice springSecurity projectLearning SQL
    FRIENDS