大姚网站建设,扬州建设信息网站,现在什么网站做外贸的最好,软件外包合同范本leetcode 139.单词拆分leetcode 139.单词拆分给定一个非空字符串 s 和一个包含非空单词的列表 wordDict#xff0c;判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明#xff1a;拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例 1…leetcode 139.单词拆分leetcode 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。注意你可以重复使用字典中的单词。这个题很明显是一个背包问题其中非空字符串s就是背包包含非空单词的列表wordDict里的元素就是一个个物品。本题问s能不能被拆分为在wordDict中出现的元素的组合问的就是“背包能否装满”动规五部曲确定dp数组以及下标的含义dp[i] : 字符串长度为i的话dp[i]为true表示可以拆分为一个或多个在字典中出现的单词。确定递推公式如果确定dp[j] 是true且 [j, i] 这个区间的子串出现在字典里那么dp[i]一定是true。j i 。所以递推公式是 if([j, i] 这个区间的子串出现在字典里 dp[j]是true) 那么 dp[i] true。dp数组如何初始化从递推公式中可以看出dp[i] 的状态依靠 dp[j]是否为true那么dp[0]就是递推的根基dp[0]一定要为true否则递推下去后面都都是false了。下标非0的dp[i]初始化为false只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。确定遍历顺序完全背包问题还要讨论两层for循环的前后顺序。如果求组合数就是外层for循环遍历物品内层for遍历背包。如果求排列数就是外层for遍历背包内层for循环遍历物品。而本题其实我们求的是排列数为什么呢拿 s applepenapple, wordDict [apple, pen] 举例。apple, pen 是物品那么我们要求 物品的组合一定是 apple pen apple 才能组成 applepenapple。所以本题的遍历顺序是外层for循环遍历背包内层for循环遍历物品。举例推导dp[i]以输入: s leetcode, wordDict [leet, code]为例dp状态如图整体代码如下class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {unordered_setstring set(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 str s.substr(j, i - j);if(set.find(str) ! set.end() dp[j] true)dp[i] true;}}return dp[s.size()];}
};多重背包问题有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用每件耗费的空间是Ci 价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量且价值总和最大。多重背包和01背包是非常像的 为什么和01背包像呢每件物品最多有Mi件可用把Mi件摊开其实就是一个01背包问题了。例如背包最大重量为10。物品为重量价值数量物品01152物品13203物品24302求解背包里能装下的物品的最大价值是多少。其实就是重量价值数量物品01151物品01151物品13201物品13201物品13201物品24301物品24301毫无区别这就转成了一个01背包问题了且每个物品只用一次。实现代码如下void test_multi_pack() {vectorint weight {1, 3, 4};vectorint value {15, 20, 30};vectorint nums {2, 3, 2};int bagWeight 10;for (int i 0; i nums.size(); i) {while (nums[i] 1) { // nums[i]保留到1把其他物品都展开weight.push_back(weight[i]);value.push_back(value[i]);nums[i]--;}}vectorint dp(bagWeight 1, 0);for(int i 0; i weight.size(); i) { // 遍历物品for(int j bagWeight; j weight[i]; j--) { // 遍历背包容量dp[j] max(dp[j], dp[j - weight[i]] value[i]);}for (int j 0; j bagWeight; j) {cout dp[j] ;}cout endl;}cout dp[bagWeight] endl;}
int main() {test_multi_pack();
}
