php旅游类网站开发,金融网站推广圳seo公司,苏州做网站优化哪家好,自己画户型图的app139.单词拆分
题目链接#xff1a;
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
求解思路#xff1a;
单词是物品#xff0c;字符串s是背包#xff0c;单词能否组成字符串s#xff0c;就是问物品能不能把背包装满。
动规五部曲
确定dp数…139.单词拆分
题目链接
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
求解思路
单词是物品字符串s是背包单词能否组成字符串s就是问物品能不能把背包装满。
动规五部曲
确定dp数组及其下标含义字符串长度为idp[i] 表示可以字符串可以拆分为一个或多个在字典中出现的单词确定递推公式如果确定dp[j] 是true且[j, i]这个区间的子串出现在字典里那么dp[i]一定是true。所以递推公式是 if([j, i] 这个区间的子串出现在字典里 dp[j]是true) 那么 dp[i] truedp数组的初始化dp[0] true递推的根基其他下表都初始化为false确定遍历顺序本题强调顺序因此是排列问题所以先遍历背包再遍历物品因为是完全背包所以正序遍历举例推导dp以输入: s leetcode, wordDict [leet, code]为例dp状态如图 代码
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);if (wordSet.find(word) ! wordSet.end() dp[j]){dp[i] true;}}}return dp[s.size()];}
};
背包总结
背包递推公式
问能否能装满背包或者最多装多少dp[j] max(dp[j], dp[j - nums[i]] nums[i]); 对应题目如下
动态规划416.分割等和子集(opens new window)动态规划1049.最后一块石头的重量 II(opens new window)
问装满背包有几种方法dp[j] dp[j - nums[i]] 对应题目如下
动态规划494.目标和(opens new window)动态规划518. 零钱兑换 II(opens new window)动态规划377.组合总和Ⅳ(opens new window)动态规划70. 爬楼梯进阶版完全背包(opens new window)
问背包装满最大价值dp[j] max(dp[j], dp[j - weight[i]] value[i]); 对应题目如下
动态规划474.一和零(opens new window)
问装满背包所有物品的最小个数dp[j] min(dp[j - coins[i]] 1, dp[j]); 对应题目如下
动态规划322.零钱兑换(opens new window)动态规划279.完全平方数
遍历顺序
01背包
二维dp数组01背包先遍历物品还是先遍历背包都是可以的且第二层for循环是从小到大遍历。
一维dp数组01背包只能先遍历物品再遍历背包容量且第二层for循环是从大到小遍历。
完全背包
纯完全背包的一维dp数组实现先遍历物品还是先遍历背包都是可以的且第二层for循环是从小到大遍历。
如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品。
相关题目如下
求组合数
动态规划518.零钱兑换II(opens new window)
求排列数
动态规划377. 组合总和 Ⅳ (opens new window)动态规划70. 爬楼梯进阶版完全背包(opens new window)
如果求最小数那么两层for循环的先后顺序就无所谓了相关题目如下
求最小数
动态规划322. 零钱兑换 (opens new window)动态规划279.完全平方数(opens new window)
