解决背包衍生题目:单词拆分和分割等和子集--动态规划方式深度呈现

这篇具有很好参考价值的文章主要介绍了解决背包衍生题目:单词拆分和分割等和子集--动态规划方式深度呈现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

139. 单词拆分

解题思路

代码实现

416. 分割等和子集

二维动态规划

状态压缩(一维)

问题拓展

背包九讲知识总结

相关问题


139. 单词拆分

题目描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

示例 1:

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2:

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。

注意,你可以重复使用字典中的单词。

示例 3:

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示:

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s 和 wordDict[i] 仅由小写英文字母组成
  • wordDict 中的所有字符串 互不相同

解题思路

解决背包衍生题目:单词拆分和分割等和子集--动态规划方式深度呈现,# 算法,力扣,动态规划

dp[i] 表示字符串 s 的前 i 个字符是否可以用 wordDict 中的单词拼接得到。

解题步骤如下:

  1. 初始化一个大小为 s.length() + 1 的布尔数组 dp,并将 dp[0] 设置为 true,表示空字符串总是可以拼接的。

  2. 对于每个从 1s.length() 的索引 i,遍历检查:

    • 对于每个在 wordDict 中的单词 word,如果 word 的长度小于等于 idp[i - word.length()]true,则检查 s 从位置 i - word.length()i 的子串是否等于 word
    • 如果这个子串等于 word,则将 dp[i] 设置为 true
  3. 在完成上述步骤后,dp[s.length()] 将给出答案,表示整个字符串 s 是否可以由 wordDict 中的单词拼接得到。

代码实现

import java.util.List;


public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;

        for (int i = 1; i <= s.length(); i++) {
            for (String word : wordDict) {
                if (word.length() <= i) {
                    if (dp[i - word.length()]) {
                        if (s.substring(i - word.length(), i).equals(word)) {
                            dp[i] = true;
                            break;
                        }
                    }
                }
            }
        }
        return dp[s.length()];
    }
}

416. 分割等和子集

题目描述

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

示例 1:

输入:nums = [1,5,11,5]
输出:true
解释:数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2:

输入:nums = [1,2,3,5]
输出:false
解释:数组不能分割成两个元素和相等的子集。

提示:

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

二维动态规划

解决背包衍生题目:单词拆分和分割等和子集--动态规划方式深度呈现,# 算法,力扣,动态规划

状态转移方程:很多时候,状态转移方程思考的角度是「分类讨论」,对于「0-1 背包问题」而言就是「当前考虑到的数字选与不选」。

dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数,每个数只能用一次,使得这些数的和恰好等于 j

  1. 不选择 nums[i],如果在 [0, i - 1] 这个子区间内已经有一部分元素,使得它们的和为 j ,那么 dp[i][j] = true;
  2. 选择 nums[i],如果在 [0, i - 1] 这个子区间内就得找到一部分元素,使得它们的和为 j - nums[i]。

状态转移方程:

dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]

以下是解决这个问题的步骤: 

  1. 计算总和:首先,计算数组 nums 的总和。如果总和是奇数,那么不能分割成两个和相等的子集,因为两个整数和不能为奇数。

  2. 初始化动态规划数组:创建一个布尔型动态规划数组 dp,其大小为 sum / 2 + 1dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数,每个数只能用一次,使得这些数的和恰好等于 j。初始化 dp[0]true,因为总和为 0 总是可能的。

  3. 填充动态规划数组:对于 nums 中的每个数字 num,从 sum / 2num 倒序遍历 dp 数组,更新 dp[j] = dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]

  4. 检查结果:最后,返回 dp[len - 1][target]的值。如果 dp[len - 1][target]true,表示可以分割数组成两个和相等的子集。 

public class Solution {
    public boolean canPartition(int[] nums) {
        int len = nums.length;
        // 计算数组总和
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        // 如果总和是奇数,无法平分为两个和相等的子集
        if ((sum & 1) == 1) {
            return false;
        }

        int target = sum / 2;
        // 创建动态规划数组,dp[i][j] 表示使用前 i 个数字能否得到总和 j
        boolean[][] dp = new boolean[len][target + 1];

        //初始化第一行,只使用第一个数字 nums[0] 时,能达到的总和
        //防止数组越界要加个判断
        if (nums[0] <= target) {
            dp[0][nums[0]] = true;
        }

        // 动态规划,填充剩余的表格
        for (int i = 1; i < len; i++) {
            for (int j = 0; j <= target; j++) {
                // 先从上一行继承结果
                dp[i][j] = dp[i - 1][j];

                // 如果当前数字等于目标值 j,直接标记为 true
                if (nums[i] == j) {
                    dp[i][j] = true;
                    continue;
                }
                // 如果当前数字小于 j,考虑两种情况:不取或取当前数字
                if (nums[i] < j) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }
        }
        // 返回最终结果,即使用所有数字是否能达到总和 target
        return dp[len - 1][target];
    }
}

状态压缩(一维)

本质上,这个问题是一个子集求和问题,类似于背包问题。问题可以被转化为:是否可以从数组中选择一些数字,使得这些数字的总和等于数组所有元素总和的一半。

dp[i] 表示数组是否可以形成总和为 i 的子集。初始化 dp[0] 为 true,因为总和为 0 总是可能的。

public class Solution {
    public boolean canPartition(int[] nums) {
        // 计算数组总和
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        // 如果总和是奇数,则不能分割成两个和相等的子集
        if (sum % 2 != 0) {
            return false;
        }

        // 计算子集总和目标值(数组总和的一半)
        sum /= 2;

        // 初始化动态规划数组
        boolean[] dp = new boolean[sum + 1];
        dp[0] = true; // 总和为0总是可能的

        // 遍历数组中的每个数字
        for (int i = 1; i < len; i++) {
            // 从子集总和目标值向下遍历到当前数字
            for (int j = sum; nums[i] <= j; j--) {
                // 更新动态规划数组的值
                // dp[j] = true 代表不包含当前考虑的 num 就已经能组成子集

                //dp[j - num] = true  代表的是包含当前考虑的 num 的解
                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }

        // 如果dp[sum]为true,则表示可以分割数组成两个和相等的子集
        return dp[sum];
    }
}

思考:为什么压缩到一维时,内循环要采用逆序?

因为在一维情况下,是根据 dp[j] || dp[j - nums[i]]来推d[j]的值,如不逆序,就无法保证在外循环 i 值保持不变 j 值递增的情况下,dp[j - num[i]]的值不会被当前所放入的nums[i]所修改,当j值未到达临界条件前,会一直被nums[i]影响,也即是可能重复的放入了多次nums[i],为了避免前面对后面产生影响,故用逆序。

举个例子,数组为[2,2,3,5],要找和为6的组合

  • i = 0时,dp[2]为true,
  • 当i自增到1,j = 4时,nums[i] = 2,dp[4] = (dp[4] || dp[4 - 2]) 为true,
    • 当i不变,j = 6时,dp[6] = dp [6] || dp [6 - 2],而dp[4]为true,

所以dp[6] = true,显然是错误的。 如果是正序的话,后面dp访问前面的dp时得到的是已经更新的内故必须得纠正在正序时,i值不变时多次放入nums[i]影响后续判断的情况。

但如果我们逆序遍历 j

  • i = 1nums[i] = 2,逆序遍历 j
    • j = 6dp[6] = dp[6] || dp[6 - 2],此时 dp[6 - 2]dp[4] 还没有被当前的 nums[i] 更新,所以这是基于 i = 0 时的结果。
    • 接下来,当 j = 4,更新 dp[4],但这个更新不会影响到 j = 6 的计算。

逆序遍历保证了在计算 dp[j] 时,我们使用的 dp[j - nums[i]] 是基于之前元素的结果,而不是当前元素 nums[i] 的结果。这样就避免了重复计算同一个元素。

解决背包衍生题目:单词拆分和分割等和子集--动态规划方式深度呈现,# 算法,力扣,动态规划

问题拓展

这道题本质是个子集求和问题:求nums的一个子集他们的和是target。

第 494 题:目标和也可以转为为子集求和数学推导略,下面是子集求和的代码模板。

// 创建动态规划数组,dp[i] 表示和为 i 的子集的数量
int[] dp = new int[target + 1];
// 初始化,和为0的方式有一种(不选择任何元素)
dp[0] = 1;

// 遍历nums中的每个数字
for (int num : nums) {
    // 从新目标开始向下更新dp数组
    for (int i = target; i >= num; i--) {
         // 更新dp[i]:加上当前数字num能够达到的子集数
         dp[i] += dp[i - num];
    }
}

// 返回达到新目标的子集数
return dp[target];

背包九讲知识总结

  1. 0-1背包问题:这是最基本的形式,每件物品都是独一无二的,可以选择放入或不放入。状态F[i, v]表示将前i件物品放入容量为v的背包可以获得的最大价值。状态转移方程为F[i, v] = max{F[i − 1, v], F[i − 1, v − Ci] + Wi}(内循环用逆序)

  2. 完全背包问题:与01背包问题类似,但每种物品可以被多次选择。状态转移方程需要改变,以适应同一物品可以多次选择的可能性(内循环用顺序)

  3. 多重背包问题:涉及可以多次选择但有特定限制的物品。解决方案可以通过将其转换为01背包问题或使用单调队列实现O(VN)的解决方案。

  4. 混合三种背包问题:涉及01背包、完全背包和多重背包问题的混合。解决策略根据物品类型的不同而变化,对不同类型的物品使用不同的循环。

  5. 二维费用的背包问题:为每件物品引入第二种成本维度。解决方案涉及为状态添加额外的维度以适应附加成本。

  6. 分组的背包问题:物品被划分为组,每组内的物品相互冲突,每组最多选择一件。解决方案涉及将每组视为单独实体,并对每组应用背包解决方案。

  7. 有依赖的背包问题:涉及选择某些物品依赖于选择其他物品。解决方案是通过将依赖物品转换为组,并将其解决为分组背包问题。

  8. 泛化物品:这个概念处理的是成本和价值不固定但随分配的成本变化的物品。这是对背包问题的更抽象的处理方式。

  9. 背包问题问法的变化:这一部分讨论了提出背包问题的不同方式,例如找出填满背包的方法数、最小化总价值或找出字典序最小的最优解。

链接: 网盘地址 提取码: tcnq 

相关问题

「力扣」上的 0-1 背包问题:

「力扣」第 416 题:分割等和子集(中等);
「力扣」第 474 题:一和零(中等);
「力扣」第 494 题:目标和(中等);
「力扣」第 879 题:盈利计划(困难);

「力扣」上的 完全背包问题:

「力扣」第 322 题:零钱兑换(中等);
「力扣」第 518 题:零钱兑换 II(中等);
「力扣」第 1449 题:数位成本和为目标值的最大数字(困难)。
 文章来源地址https://www.toymoban.com/news/detail-780093.html

到了这里,关于解决背包衍生题目:单词拆分和分割等和子集--动态规划方式深度呈现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 01背包问题-递推公式的自我理解与LeetCode 416. 分割等和子集

    学算法好痛苦,完全是对我智力的一次次折磨,看了好多博客,对二维dp数组的理解都是直接搬了代码随想录,搬了随想录又没详细解释,大家都是一眼看懂的吗,好吧() 如果有一个容量为 j 的这样的背包——一个独立的,容量为j的背包。(没把它理解为“剩余容量”) 对于

    2024年02月07日
    浏览(44)
  • 力扣算法刷题Day42|动态规划:01背包问题 分割等和子集

    力扣题目:01背包问题(二维数组) 刷题时长:参考题解 解题方法:动态规划 + 二维dp数组 复杂度分析 时间 空间 问题总结 理解递推公式困难 本题收获 动规思路:两层for循环,第一层i遍历物品,第二层j枚举背包容量以内所有值 确定dp数组及下标的含义:dp[i][j] 表示从下标

    2024年02月13日
    浏览(62)
  • 【Day42】代码随想录之动态规划0-1背包_416. 分割等和子集

    动态规划理论基础 动规五部曲: 确定dp数组 下标及dp[i] 的含义。 递推公式:比如斐波那契数列 dp[i] = dp[i-1] + dp[i-2]。 初始化dp数组。 确定遍历顺序:从前到后or其他。 推导dp数组。 出现结果不正确: 打印dp日志和自己想的一样:递推公式、初始化或者遍历顺序出错。 打印

    2024年02月20日
    浏览(68)
  • 代码随想录 Day35 动态规划04 01背包问题和完全背包问题 LeetCode T416 分割等和子集

    说到背包问题大家都会想到使用动规的方式来求解,那么为什么用动规呢, dp数组代表什么呢 ? 初始化是什么 , 遍历方式又是什么 ,这篇文章笔者将详细讲解背包问题的经典例题0-1背包问题和完全背包问题的解题方式,希望能帮助到大家 有人一提到背包问题就只会使用动态规划来

    2024年02月06日
    浏览(76)
  • Day42|动态规划part04: 01背包问题,你该了解这些!、滚动数组、416. 分割等和子集

    其他背包,面试几乎不会问,都是竞赛级别的了,leetcode上连多重背包的题目都没有,所以题库也告诉我们,01背包和完全背包就够用了。 而完全背包又是也是01背包稍作变化而来,即:完全背包的物品数量是无限的。 01 背包问题描述 有n件物品和一个最多能背重量为w 的背包

    2024年04月25日
    浏览(38)
  • 第九章 动态规划part04(● 01背包问题,你该了解这些! ● 01背包问题,你该了解这些! 滚动数组 ● 416. 分割等和子集 )

    ● 01背包问题,你该了解这些! ● 01背包问题,你该了解这些! 滚动数组 ● 416. 分割等和子集 https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html 视频讲解:https://www.bilibili.com/video/BV1cg411g7Y6 1.确定dp数组以及下标的含义 i是物品,j是背包容量

    2024年01月16日
    浏览(52)
  • 算法设计与分析实验4 :利用动态规划的方法解决子集等和分割判断问题

    实验4  利用动态规划的方法解决子集等和分割判断问题 一、实验目的 1. 了解动态规划的主要思想。 2. 掌握背包问题解决方法用以解决该问题。 3. 分析核心代码的时间复杂度和空间复杂度。 二、实验内容和要求 题目:给定一个只包含正整数的非空数组。是否可以将这个数组

    2024年04月23日
    浏览(42)
  • 动态规划(分割等和子集)

    题目难易:中等 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200 示例 1: 输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11]. 示例 2: 输入: [1, 2

    2024年02月02日
    浏览(42)
  • Leetcode 416 分割等和子集

    题意理解 :         给你一个  只包含正整数  的  非空  数组  nums  。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。         即将数组的元素分成两组,每组数值=sum(nums)/2         若能分成这样的两组,则返回true,否则返回false      

    2024年02月01日
    浏览(44)
  • 【LeetCode】416.分割等和子集

    给你一个  只包含正整数  的  非空  数组  nums  。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 示例 1: 示例 2: 提示: 1 = nums.length = 200 1 = nums[i] = 100 实际上是求能否从背包里选取元素,使这些元素之和等于数组所有元素之和的一半。dp

    2024年02月11日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包