网站服务建设,网站问题有哪些内容,家教网站建设的推广,快手作品推广网站文章目录 139.单词拆分思路代码实现 背包问题总结背包类型递推公式 139.单词拆分
题目链接
思路
确定dp数组以及下标的含义 dp[i] : 从0开始长度为i的字符串是否可以拆分为一个或多个在字典中出现的单词确定递推公式 如果确定dp[j] 是true#xff0c;且 [j, i] 这个区间的子… 文章目录 139.单词拆分思路代码实现 背包问题总结背包类型递推公式 139.单词拆分
题目链接
思路
确定dp数组以及下标的含义 dp[i] : 从0开始长度为i的字符串是否可以拆分为一个或多个在字典中出现的单词确定递推公式 如果确定dp[j] 是true且 [j, i] 这个区间的子串出现在字典里那么dp[i]一定是true。j i 。 递推公式是 if([j, i] 这个区间的子串出现在字典里 dp[j]是true)dp数组如何初始化 dp[0]一定要为true否则递推下去后面都都是false了。下标非0的dp[i]初始化为false确定遍历顺序 本题其实我们求的是排列数。 拿 s “applepenapple”, wordDict [“apple”, “pen”] 举例 “apple”, “pen” 是物品那么我们要求 物品的组合一定是 “apple” “pen” “apple” 才能组成 “applepenapple”。 “apple” “apple” “pen” 或者 “pen” “apple” “apple” 是不可以的那么我们就是强调物品之间顺序。 所以说本题一定是先遍历背包再遍历物品。举例推导dp[i]
代码实现
有一个困惑点为什么不能用wordSet.size()而必须用s.size()
class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {unordered_setstring wordSet(wordDict.begin(), wordDict.end());vectorbool dp(s.size() 1, false);dp[0] true;for (int i 1; i s.size(); i) { // 遍历背包for (int j 0; j i; j) { // 遍历物品string word s.substr(j, i - j); //substr(起始位置截取的个数)if (wordSet.find(word) ! wordSet.end() dp[j]) {dp[i] true;}}}return dp[s.size()];}
};背包问题总结
背包类型
01背包 有限个种类数的物品每个只有一个装在有限个单一背包里 一维数组基本上都是外层背包内层物品外层循环从前到后遍历内层循环从后向前遍历以防重复计算 对应题目 等和分割子串 最后一块石头的重量 II 目标和 一和零这道题是二维的问题有点抽象完全背包 有限个种类数的物品每个有无数个装在有限个单一背包里 组合问题一般外层循环是物品遍历顺序从前到后内层循环是背包遍历顺序从前到后 排列问题一般外层循环是背包遍历顺序从前到后内层循环是物品遍历顺序从前到后 对应题目 组合问题零钱兑换II 排列问题组合总和 Ⅳ、爬楼梯、零钱兑换、完全平方数、⭐️单词拆分这道题看不太出可以用动态规划但是把字符串长度看成背包字符串内单词看成物品也可以用动态规划方法来解决因为我们最后想得到的结果只是一个bool值内部单词顺序不同对答案有影响所以是个排列问题多重背包 有限个种类数的物品每个有多个装在有限个单一背包里 其实把它转化为01背包就好了。 如下图的要求 转化为01背包则为
递推公式
问能否能装满背包或者最多装多少dp[j] max(dp[j], dp[j - nums[i]] nums[i]);对应题目如下 等和分割子串 最后一块石头的重量 II 问装满背包有几种方法dp[j] dp[j - nums[i]] 对应题目如下 零钱兑换II 目标和 组合总和 Ⅳ 爬楼梯 问背包装满最大价值dp[j] max(dp[j], dp[j - weight[i]] value[i]); 对应题目如下 一和零 问装满背包所有物品的最小个数dp[j] min(dp[j - coins[i]] 1, dp[j]); 对应题目如下 零钱兑换 完全平方数
