白云做网站公司,政务网站建设模块,企业cms建站系统,微信做个小程序多少钱代码随想录算法训练营第四十六天| 139.单词拆分 背包问题总结
一、力扣139.单词拆分
题目链接#xff1a; 思路#xff1a;确定dp数组#xff0c;dp[i]为true表示从0到i切分的字串都在字典中出现过。 确定递推公式#xff0c;dp[i] 为true要求 s[j, i] 在字典中出现…代码随想录算法训练营第四十六天| 139.单词拆分 背包问题总结
一、力扣139.单词拆分
题目链接 思路确定dp数组dp[i]为true表示从0到i切分的字串都在字典中出现过。 确定递推公式dp[i] 为true要求 s[j, i] 在字典中出现且dp[j]为true即可设置dp[i]true 初始化dp[0]true这个设置为true是为了让后面依赖前面的状态。 遍历时注意字典中的单词可以在s的前面出现也可以在后面出现这就是排列问题单组合物品在前面出现就不会在后面出现。另外注意substring是左闭右开。
class Solution {public boolean wordBreak(String s, ListString wordDict) {HashSetString set new HashSet(wordDict);boolean[] dp new boolean[s.length()1];dp[0] true;for (int i 1; i s.length(); i) {for (int j 0; j i !dp[i]; j) {if (set.contains(s.substring(j, i)) dp[j]) {dp[i] true;}}}return dp[s.length()];}
}二、背包问题总结
背包五部曲 1、确定dp数组dp table以及下标的含义 2、确定递推公式 3、dp数组如何初始化 4、确定遍历顺序 5、举例推导dp数组
背包递推公式 问能否能装满背包或者最多装多少dp[j] max(dp[j], dp[j - nums[i]] nums[i]); 问装满背包有几种方法 dp[j] dp[j - nums[i]] 问背包装满最大价值 dp[j] max(dp[j], dp[j - weight[me]] value[me]); 问装满背包所有物品的最小个数 dp[j] min(dp[j - coins[me]] 1, dp[j]);
遍历顺序 01背包 二维数组的01背包先遍历物品还是先遍历背包都是可以的且第二层for循环是从小到大遍历。 一维dp数组的01背包只能先遍历物品再遍历背包容量且第二层for循环是从大到小遍历。
完全背包
一维dp数组的完全背包先遍历物品还是先遍历背包都是可以的且第二层for循环是从小到大遍历。
如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品。
如果求最小数那么两层for循环的先后顺序就无所谓了
