目录
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
中的单词拼接得到。
解题步骤如下:
-
初始化一个大小为
s.length() + 1
的布尔数组dp
,并将dp[0]
设置为true
,表示空字符串总是可以拼接的。 -
对于每个从
1
到s.length()
的索引i
,遍历检查:- 对于每个在
wordDict
中的单词word
,如果word
的长度小于等于i
且dp[i - word.length()]
为true
,则检查s
从位置i - word.length()
到i
的子串是否等于word
。 - 如果这个子串等于
word
,则将dp[i]
设置为true
。
- 对于每个在
-
在完成上述步骤后,
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
。
- 不选择 nums[i],如果在 [0, i - 1] 这个子区间内已经有一部分元素,使得它们的和为 j ,那么 dp[i][j] = true;
- 选择 nums[i],如果在 [0, i - 1] 这个子区间内就得找到一部分元素,使得它们的和为 j - nums[i]。
状态转移方程:
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]
以下是解决这个问题的步骤:
-
计算总和:首先,计算数组
nums
的总和。如果总和是奇数,那么不能分割成两个和相等的子集,因为两个整数和不能为奇数。 -
初始化动态规划数组:创建一个布尔型动态规划数组
dp
,其大小为sum / 2 + 1
。dp[i][j]
表示从数组的[0, i]
这个子区间内挑选一些正整数,每个数只能用一次,使得这些数的和恰好等于j
。初始化dp[0]
为true
,因为总和为 0 总是可能的。 -
填充动态规划数组:对于
nums
中的每个数字num
,从sum / 2
到num
倒序遍历dp
数组,更新dp[j] =
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]] -
检查结果:最后,返回 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 = 1
,nums[i] = 2
,逆序遍历j
:
- 当
j = 6
,dp[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];
背包九讲知识总结
-
0-1背包问题:这是最基本的形式,每件物品都是独一无二的,可以选择放入或不放入。状态F[i, v]表示将前i件物品放入容量为v的背包可以获得的最大价值。状态转移方程为F[i, v] = max{F[i − 1, v], F[i − 1, v − Ci] + Wi}(内循环用逆序)。
-
完全背包问题:与01背包问题类似,但每种物品可以被多次选择。状态转移方程需要改变,以适应同一物品可以多次选择的可能性(内循环用顺序)。
-
多重背包问题:涉及可以多次选择但有特定限制的物品。解决方案可以通过将其转换为01背包问题或使用单调队列实现O(VN)的解决方案。
-
混合三种背包问题:涉及01背包、完全背包和多重背包问题的混合。解决策略根据物品类型的不同而变化,对不同类型的物品使用不同的循环。
-
二维费用的背包问题:为每件物品引入第二种成本维度。解决方案涉及为状态添加额外的维度以适应附加成本。
-
分组的背包问题:物品被划分为组,每组内的物品相互冲突,每组最多选择一件。解决方案涉及将每组视为单独实体,并对每组应用背包解决方案。
-
有依赖的背包问题:涉及选择某些物品依赖于选择其他物品。解决方案是通过将依赖物品转换为组,并将其解决为分组背包问题。
-
泛化物品:这个概念处理的是成本和价值不固定但随分配的成本变化的物品。这是对背包问题的更抽象的处理方式。
-
背包问题问法的变化:这一部分讨论了提出背包问题的不同方式,例如找出填满背包的方法数、最小化总价值或找出字典序最小的最优解。
链接: 网盘地址 提取码: tcnq
相关问题
「力扣」上的 0-1 背包问题:
「力扣」第 416 题:分割等和子集(中等);
「力扣」第 474 题:一和零(中等);
「力扣」第 494 题:目标和(中等);
「力扣」第 879 题:盈利计划(困难);
「力扣」上的 完全背包问题:文章来源:https://www.toymoban.com/news/detail-780093.html
「力扣」第 322 题:零钱兑换(中等);
「力扣」第 518 题:零钱兑换 II(中等);
「力扣」第 1449 题:数位成本和为目标值的最大数字(困难)。
文章来源地址https://www.toymoban.com/news/detail-780093.html
到了这里,关于解决背包衍生题目:单词拆分和分割等和子集--动态规划方式深度呈现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!