建站公司还有前途吗,wordpress大淘客采集,金坛住房和城乡建设局网站,解决做网站问题目录
算法题 Leetcode 139.单词拆分
个人思路
解法
动态规划
回溯法
多重背包理论基础
背包问题总结篇
解题思路
背包递推公式
遍历顺序
01背包
完全背包 算法题 Leetcode 139.单词拆分
题目链接:139.单词拆分
大佬视频讲解#xff1a;单词拆分视频讲解 个人思…目录
算法题 Leetcode 139.单词拆分
个人思路
解法
动态规划
回溯法
多重背包理论基础
背包问题总结篇
解题思路
背包递推公式
遍历顺序
01背包
完全背包 算法题 Leetcode 139.单词拆分
题目链接:139.单词拆分
大佬视频讲解单词拆分视频讲解 个人思路
这道题有点绕,思路没打开... 解法 这道题目的时候可以使用回溯法解决和之前做的一题很像分割回文串 是枚举分割后的所有子串判断是否回文。而这里是判断是否在字典出现。除开回溯法动态规划也能解决这道题。 动态规划
单词就是物品字符串s就是背包单词能否组成字符串s就是问物品能不能把背包装满。拆分时可以重复使用字典中的单词说明就是一个完全背包 动规五部曲
1.确定dp数组以及下标的含义
dp[i] : 字符串长度为i的话dp[i]为true表示可以拆分为一个或多个在字典中出现的单词 2.确定递推公式 如果确定dp[j] 是true且 [j, i] 这个区间的子串出现在字典里那么dp[i]一定是truej i 所以递推公式是 if([j, i] 这个区间的子串出现在字典里 dp[j]是true) 那么 dp[i] true 3.dp数组如何初始化 从递推公式中可以看出dp[i] 的状态依靠 dp[j]是否为true那么dp[0]就是递推的根基dp[0]一定要为true否则递推下去后面都都是false了。 下标非0的dp[i]初始化为false只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。 4.确定遍历顺序
如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品。 本题求的是排列数: 拿 s applepenapple, wordDict [apple, pen] 举例。 apple, pen 是物品那么我们要求 物品的组合一定是 apple pen apple 才能组成 applepenapple。 apple apple pen 或者 pen apple apple 是不可以的所以强调物品之间顺序。 所以说本题一定是 先遍历 背包再遍历物品。 5.举例推导dp[i]
以输入: s leetcode, wordDict [leet, code]为例dp状态如图 class Solution {public boolean wordBreak(String s, ListString wordDict) {HashSetString set new HashSet(wordDict);boolean[] valid new boolean[s.length() 1];valid[0] true;//初始化for (int i 1; i s.length(); i) {//遍历背包(字符串s)for (int j 0; j i !valid[i]; j) {//遍历物品if (set.contains(s.substring(j, i)) valid[j]) {valid[i] true;}}}return valid[s.length()];}
} 时间复杂度:O(n^2)嵌套for循环 空间复杂度:O( n);存储一个长度为n1的dp数组 回溯法 class Solution {private SetString set;private int[] memo;public boolean wordBreak(String s, ListString wordDict) {memo new int[s.length()];set new HashSet(wordDict);return backtracking(s, 0);}public boolean backtracking(String s, int startIndex) {// System.out.println(startIndex);if (startIndex s.length()) {return true;}if (memo[startIndex] -1) {return false;}for (int i startIndex; i s.length(); i) {String sub s.substring(startIndex, i 1);// 拆分出来的单词无法匹配if (!set.contains(sub)) {continue; }boolean res backtracking(s, i 1);if (res) return true;}// 这里是关键找遍了startIndex~s.length()也没能完全匹配标记从startIndex开始不能找到memo[startIndex] -1;return false;}
} 时间复杂度:O(n)其中n是字符串s的长度 空间复杂度:O( nm);其中n是字符串s的长度m是字典中词的数量 多重背包理论基础
题目
有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用每件耗费的空间是Ci 价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量且价值总和最大。
多重背包和01背包是非常像的因为这里的 每件物品最多有Mi件可用把Mi件摊开其实就是一个01背包问题了。
例如
背包最大重量为10。
物品为
重量价值数量物品01152物品13203物品24302
问背包能背的物品最大价值是多少
和如下情况是一样的这就转成了一个01背包问题了且每个物品只用一次。
重量价值数量物品01151物品01151物品13201物品13201物品13201物品24301物品24301
说明
多重背包相当于是一种01背包用01背包的基础上写出对应代码就可以了。 解决代码
import java.util.Scanner;
class multi_pack{public static void main(String [] args) {Scanner sc new Scanner(System.in);int bagWeight, n;//bagWeight背包容量 ;n:物品种类bagWeight sc.nextInt();//获取用户输入数据中间用空格隔开回车键换行n sc.nextInt();int[] weight new int[n];int[] value new int[n];int[] nums new int[n];for (int i 0; i n; i) weight[i] sc.nextInt();for (int i 0; i n; i) value[i] sc.nextInt();for (int i 0; i n; i) nums[i] sc.nextInt();int[] dp new int[bagWeight 1];//初始化dp数组for (int i 0; i n; i) { //先遍历物品再遍历背包作为01背包处理for (int j bagWeight; j weight[i]; j--) {//遍历每种物品的个数for (int k 1; k nums[i] (j - k * weight[i]) 0; k) {dp[j] Math.max(dp[j], dp[j - k * weight[i]] k * value[i]);}}}System.out.println(dp[bagWeight]);}
} 时间复杂度:O(n^2)嵌套循环for 其中W是背包的最大容量 空间复杂度:O( n);dp数组大小 背包问题总结篇
解题思路
卡哥的五部曲十分好用以后都这样来逐步分析.
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组
其实这五部里哪一步都很关键但确定递推公式和确定遍历顺序都具有规律性和代表性 背包递推公式
问能否能装满背包或者最多装多少dp[j] max(dp[j], dp[j - nums[i]] nums[i]);
对应题目有力扣416.分割等和子集1049.最后一块石头的重量 II 问装满背包有几种方法dp[j] dp[j - nums[i]]
对应题目有力扣 494.目标和518. 零钱兑换 II377.组合总和Ⅳ 问背包装满最大价值dp[j] max(dp[j], dp[j - weight[i]] value[i]);
对应题目有力扣 474.一和零 问装满背包所有物品的最小个数dp[j] min(dp[j - coins[i]] 1, dp[j]);
对应题目有力扣 322.零钱兑换279.完全平方数
遍历顺序
01背包
二维dp数组01背包先遍历物品还是先遍历背包都是可以的且第二层for循环是从小到大遍历。
一维dp数组01背包只能先遍历物品再遍历背包容量且第二层for循环是从大到小遍历倒序。 完全背包
纯完全背包的一维dp数组实现先遍历物品还是先遍历背包都是可以的且第二层for循环是从小到大遍历。但是仅仅是纯完全背包的遍历顺序是这样的题目稍有变化两个for循环的先后顺序就不一样了。 如果求组合数就是外层for循环遍历物品内层for遍历背包。 如果求排列数就是外层for遍历背包内层for循环遍历物品。 相关力扣题目如下
求组合数518.零钱兑换II求排列数377. 组合总和 Ⅳ
如果求最小数那么两层for循环的先后顺序就无所谓了相关题目如下
求最小数322. 零钱兑换、279.完全平方数
对于背包问题其实递推公式算是容易的难是难在遍历顺序上如果把遍历顺序搞透才算是真正理解了。 以上是个人的思考反思与总结若只想根据系列题刷参考卡哥的网址代码随想录算法官网
