苏州知名网站制作公司,如何建设线报网站,邯郸网站建设怎么做,广州做网站优化哪家专业前言 在本期开始之前,让我们再回顾一下动规五部曲,并且今天的任务只有一道题,我们顺便也回顾一下之前学过的知识点,动规的前面集中化题型,0-1背包,完全背包,以及很多种遍历顺序,让秋秋和大家娓娓道来. 首先我们回顾一下动态规划的动规五部曲. 1.明确dp数组的元素含义 2.明确dp数…前言 在本期开始之前,让我们再回顾一下动规五部曲,并且今天的任务只有一道题,我们顺便也回顾一下之前学过的知识点,动规的前面集中化题型,0-1背包,完全背包,以及很多种遍历顺序,让秋秋和大家娓娓道来. 首先我们回顾一下动态规划的动规五部曲. 1.明确dp数组的元素含义 2.明确dp数组的递推公式 3.初始化dp数组 4.明确dp数组的遍历方式 5.打印dp数组排错逻辑 前面文章回顾: 代码随想录Day32 动态规划01 LeetCodeT509 斐波那契数列 T70 爬楼梯 T746 爬楼梯的最小消耗-CSDN博客 代码随想录Day33 LeetCode T62不同路径 LeetCode T63 不同路径II-CSDN博客 代码随想录Day34 LeetCode T343整数拆分 T96 不同的二叉搜索树-CSDN博客 代码随想录 Day35 动态规划04 01背包问题和完全背包问题 LeetCode T416 分割等和子集-CSDN博客 代码随想录Day36 动态规划05 LeetCode T1049最后一块石头的重量II T494 目标和 T474 一和零-CSDN博客 代码随想录 Day37 完全背包理论基础 卡码网T52 LeetCode T518 零钱兑换II T377 组合总和IV-CSDN博客 代码随想录 Day38 完全背包问题 LeetCode T70 爬楼梯 T322 零钱兑换 T279 完全平方数-CSDN博客 LeetCode T139 单词划分
题目链接:139. 单词拆分 - 力扣LeetCode 题目思路: 本题最简单的思路肯定是回溯算法去暴力枚举每一种结果,我们可以回顾一下之前的回溯算法 算法的复杂度是O(2^n),因为每一个元素只有两种结果,选或者不选,当然这道题不是我们今天的主菜,下面我会给出可以ac的回溯算法的代码,但是今天我们还是着重讨论动规算法的解法 1.明确dp数组的元素含义 dp[i] 的意义是dp[i] : 字符串长度为i的话dp[i]为true表示可以拆分为一个或多个在字典中出现的单词。 2.明确dp数组的递推公式 递推公式就是当[j,i]这个字符串出现在字典里,并且dp[j]是true,那么就设置为dp[i]为true 3.初始化dp数组 dp[0] true;其他的赋值为false 4.明确dp数组的遍历方式 先遍历背包后遍历物品,理由在拓展中,用用例举例,假如第一个apple写入了一个true,第二个元素pen并不能将最后一个元素赋值为true,除非再给一个apple来遍历才行 5.打印dp数组排错逻辑 题目代码:
//动规算法的解法
class Solution {public boolean wordBreak(String s, ListString wordDict) {boolean[] dp new boolean[s.length()1];//初始化Arrays.fill(dp,false);dp[0] true;//遍历for(int i 1;is.length();i){for(String word:wordDict){int len word.length();if(ilen dp[i-len] true word.equals(s.substring(i-len,i)) ){dp[i] true;}}}return dp[s.length()];}
}//回溯算法的解法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;}
}
拓展: 这里我们也谈一下为什么不能先遍历物品,后遍历背包不行? 因为这里我们先想一想之前遍历背包再遍历物品和先遍历物品在再遍历背包 分别对应了什么问题的解决 先物品后背包 --------------- 组合问题,不讲究顺序 先背包后数组 --------------- 排列问题,讲究顺序 使用用例s applepenapple, wordDict [apple, pen]对应的dp数组状态如下 最后dp[s.size()] 0 即 dp[13] 0 而不是1因为先用 apple 去遍历的时候dp[8]并没有被赋值为1 还没用pen所以 dp[13]也不能变成1。 除非是先用 apple 遍历一遍再用 pen 遍历此时 dp[8]已经是1最后再用 apple 去遍历dp[13]才能是1。 总结动规问题1 普通动规问题 斐波那契数 递推公式:dp[i] dp[i-1]dp[i-2]; 爬楼梯 递推公式:dp[i] dp[i-1]dp[i-2]; 最小花费爬楼梯 这里比上面多了一个价值和求最小值 dp[i] Math.min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]); 不同路径 dp[i][j] dp[i-1][j] dp[i][j-1]; 结果从左边和上面产生 不同路径II(加上阻碍) dp[i][j] (obstacleGrid[i][j] 0)?dp[i-1][j] dp[i][j-1]:0;遇到阻碍标记成0 整数拆分 dp[i] Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j])) 拆分成两个或多个 不同的搜索二叉树 这时候dp[i]表示j个节点有多少个不同的二叉搜索树 dp[i] dp[j-1] * dp[i-j]; 注:左子树节点数*右子树 0-1背包(一维数组遍历背包是从大到小,避免每个物品取了多次) dp[j] max(dp[j], dp[j - weight[i]] value[i]); dp[j] max(dp[j], dp[j - weight[i]] value[i]); dp[j] max(dp[j], dp[j - weight[i]] value[i]); 重要的公式说三遍 分割等和子集 求和除以2当做背包容量 查看能否装满 dp[j]表示放进物品时,最大容量 dp[j] Math.max(dp[j],dp[j-nums[i]]nums[i]); 最后一块石头的重量II 和上面一样分两半处理,最后用sum减去中间值dp的两倍即可 dp[j] Math.max(dp[j],dp[j-stones[i]]stones[j]) 目标和(此时就在原来的基础上变成了方法有多少种) 求正1的数量和-1的都可以,通过推导得到公式 left (targetsum)/2 正的阵营 dp dp[j-nums[i]] 一和零 用一维数组从两个维度思考问题,价值是有x和y两个维度 和前面一样倒序遍历不过从两个维度出发 for (int i m; i zeroNum; i--) {for (int j n; j oneNum; j--) {dp[i][j] Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] 1);}} 完全背包(在0-1背包上遍历背包改成从前向后) 零钱兑换II 求组合数 求方法数dp[j]dp[j-coins[i]]; 组合总和IV 求排列数,先背包后物品 爬楼梯(进阶) 累加即可,排列数 零钱兑换 由于求最小值,所以赋值为最大数,如果dp[j-coins[i]]没变就代表这个数没意义 dp[j] Math.min(dp[j], dp[j - coins[i]] 1); 完全平方数 最小的装满同上思路,不过这题不是隔着修改,无需判断是否有效 单词拆分 这题一定要用背包遍历物品,原因在上面
