前言
在本期开始之前,让我们再回顾一下动规五部曲,并且今天的任务只有一道题,我们顺便也回顾一下之前学过的知识点,动规的前面集中化题型,0-1背包,完全背包,以及很多种遍历顺序,让秋秋和大家娓娓道来.
首先我们回顾一下动态规划的动规五部曲.
1.明确dp数组的元素含义
2.明确dp数组的递推公式
3.初始化dp数组
4.明确dp数组的遍历方式
5.打印dp数组排错逻辑
LeetCode T139 单词划分
题目思路:
本题最简单的思路肯定是回溯算法去暴力枚举每一种结果,我们可以回顾一下之前的回溯算法
算法的复杂度是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, List<String> wordDict) { boolean[] dp = new boolean[s.length()+1]; //初始化 Arrays.fill(dp,false); dp[0] = true; //遍历 for(int i = 1;i<=s.length();i++){ for(String word:wordDict){ int len = word.length(); if(i>=len && dp[i-len] == true && word.equals(s.substring(i-len,i)) ){ dp[i] = true; } } } return dp[s.length()]; } } //回溯算法的解法 class Solution { private Set<String> set; private int[] memo; public boolean wordBreak(String s, List<String> 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 = (target+sum)/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);
完全平方数
最小的装满同上思路,不过这题不是隔着修改,无需判断是否有效
单词拆分
这题一定要用背包遍历物品,原因在上面
