算法：动态规划基础（中）：树型dfs+回溯+记忆化搜索

在前面几章中了解了所有的回溯和动态规划实际上都可以看作树形的 DFS虽然部分动态规划题目使用DFS记忆化仍然会超时但这种思想仍提供了一种可行的思路。1. 139. 单词拆分给你一个字符串s和一个字符串列表wordDict作为字典。如果可以利用字典中出现的一个或多个单词拼接出s则返回true。注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。1.1 自底向上循环尝试各个切分点确认被切掉的一部分是否被给出的词典包含在内。如果包含在内则从被切开的部分继续递归尝试切剩下的直到切到 0 说明都被切掉切包含了。根节点切分点在 s 最后一个字符 n叶子节点切分点在 s 第一个字符 1子节点当前切分点前面的所有可能的切分点class Solution { public: bool wordBreak(string s, vectorstring wordDict) { int maxLen 0; for(auto word : wordDict){ maxLen max(maxLen, (int)word.size()); } unordered_setstring words(wordDict.begin(), wordDict.end()); int n s.size(); auto dfs [](this auto dfs, int i) - bool { if(i 0) return 1; for(int j i - 1; j max(i - maxLen, 0); j--){ bool isCurContain words.contains(s.substr(j, i - j)); bool isBeforeContain dfs(j); if(isCurContain isBeforeContain) return 1; } return 0; }; return dfs(n); } };1.2 记忆化class Solution { public: bool wordBreak(string s, vectorstring wordDict) { int maxLen 0; for(auto word : wordDict){ maxLen max(maxLen, (int)word.size()); } unordered_setstring words(wordDict.begin(), wordDict.end()); int n s.size(); vectorint mem(n 1, -1); auto dfs [](this auto dfs, int i) - bool { if(i 0) return 1; if(mem[i] ! -1) return mem[i]; for(int j i - 1; j max(i - maxLen, 0); j--){ bool isCurContain words.contains(s.substr(j, i - j)); bool isBeforeContain dfs(j); if(isCurContain isBeforeContain){ mem[i] 1; return 1; } } mem[i] 0; return 0; }; return dfs(n); } };1.3 动态规划class Solution { public: bool wordBreak(string s, vectorstring wordDict) { int n s.size(); unordered_setstring uset; int maxLen 0; for(auto ss : wordDict){ uset.insert(ss); maxLen max(maxLen,(int)ss.size()); } vectorint f(n 1); // 必须n 1f[i]表示前i个因为可能一整个都是此时f[n]依赖f[0] // 否则以f[i]表示索引i则f[n-1]如果是的话此时f[0]表示索引为0的f[n-1]无法依赖 f[0] 1; for(int j 1; j n; j){ for(int i j - 1; i 0 j - i maxLen ; i--){ if(f[i] uset.count(s.substr(i, j - i))){ f[j] 1; break; } } } return f[n]; } };2. 300.最长递增子序列给你一个整数数组nums找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。2.1 自底向上题目分解题目要求数组中最长递增子序列那么我们可以求从数组每个元素开始的最长递增子序列遍历后取最大值。根节点当前开始的元素子节点从当前元素开始任一个大于它的元素叶子节点最后一个元素递归返回值从当前节点开始的最大长度class Solution { public: int lengthOfLIS(vectorint nums) { int n nums.size(); auto dfs [](this auto dfs, int cur) - int { int curMax 1; for(int nxt cur 1; nxt n; nxt){ if(nums[nxt] nums[cur]){ int subLen dfs(nxt); int curLen subLen 1; curMax max(curMax, curLen); } } return curMax; }; int ans 0; for(int i 0; i n; i){ ans max(ans, dfs(i)); } return ans; } };2.2 记忆化根节点当前开始的元素子节点从当前元素开始任一个大于它的元素叶子节点最后一个元素递归返回值从当前节点开始的最大长度记忆从当前节点开始的最大长度class Solution { public: int lengthOfLIS(vectorint nums) { int n nums.size(); vectorint mem(n1, -1); auto dfs [](this auto dfs, int cur) - int { int curMax 1; if(mem[cur] ! -1) return mem[cur]; for(int nxt cur 1; nxt n; nxt){ if(nums[nxt] nums[cur]){ int subLen dfs(nxt); int curLen subLen 1; curMax max(curMax, curLen); } } mem[cur] curMax; return curMax; }; int ans 0; for(int i 0; i n; i){ ans max(ans, dfs(i)); } return ans; } };2.3 动态规划class Solution { public: int lengthOfLIS(vectorint nums) { int n nums.size(); int ans 1; vectorint f(n, 1); for(int i 1; i n; i){ for(int j 0; j i; j){ if(nums[i] nums[j]) f[i] max(f[i], 1 f[j]); } ans max(ans, f[i]); } return ans; } };3. 152.乘积最大子数组给你一个整数数组nums请你找出数组中乘积最大的非空连续 子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。测试用例的答案是一个32-位整数。请注意一个只包含一个元素的数组的乘积是这个元素的值。3.1 自底向上同理与上一题一样将乘积最大子数组拆解为以数组中每个元素作为起点的最大子数组乘积.根节点当前元素子节点在当前元素之后的一个元素叶子节点最后一个元素递归返回值从当前节点开始的最大积和最小积因为可能负负得正注意这里要求的是连续的所以只有一个子节点class Solution { public: int maxProduct(vectorint nums) { int n nums.size(); auto dfs [](this auto dfs,int cur) - pairint, int { if(cur n) return {1, 1}; int curNum nums[cur]; int nxt cur 1; auto subPro dfs(nxt); int subPro1 subPro.first; int subPro2 subPro.second; int maxPro max(curNum, max(curNum * subPro1, curNum * subPro2)); int minPro min(curNum, min(curNum * subPro1, curNum * subPro2)); return {maxPro, minPro}; }; int ans INT_MIN; for(int i 0; i n; i){ auto curAns dfs(i); int a curAns.first; int b curAns.second; ans max(ans, max(a, b)); } return ans; } };3.2 记忆化根节点当前元素子节点在当前元素之后的一个元素叶子节点最后一个元素递归返回值从当前节点开始的最大积和最小积因为可能负负得正记忆当前节点的最大和最小积注意这里要求的是连续的所以只有一个子节点class Solution { public: int maxProduct(vectorint nums) { int n nums.size(); vectorint memMax(n 1, INT_MIN); vectorint memMin(n 1, INT_MAX); auto dfs [](this auto dfs,int cur) - pairint, int { if(cur n) return {1, 1}; if(memMax[cur] ! INT_MIN) return{memMax[cur], memMin[cur]}; int curNum nums[cur]; int nxt cur 1; auto subPro dfs(nxt); int subPro1 subPro.first; int subPro2 subPro.second; int maxPro max(curNum, max(curNum * subPro1, curNum * subPro2)); int minPro min(curNum, min(curNum * subPro1, curNum * subPro2)); memMax[cur] maxPro; memMin[cur] minPro; return {maxPro, minPro}; }; int ans INT_MIN; for(int i 0; i n; i){ auto curAns dfs(i); int a curAns.first; int b curAns.second; ans max(ans, max(a, b)); } return ans; } };3.3 动态规划class Solution { public: int maxProduct(vectorint nums) { int n nums.size(); vectorint minF(n, INT_MAX); vectorint maxF(n, INT_MIN); minF[0] nums[0]; maxF[0] nums[0]; int ans nums[0]; for(int i 1; i n; i){ int a nums[i]; int b nums[i] * minF[i - 1]; int c nums[i] * maxF[i - 1]; minF[i] min({a, b, c}); maxF[i] max({a, b, c}); ans max(ans, maxF[i]); } return ans; } };4. 416.分割等和子集给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。4.1 自顶向下翻译是否可以取出一部分使得总和为总数组和的一半。该题类似二叉树中的路径总和Ⅲ所以使用自顶向下路径总和Ⅲ中使用前缀和简化计算如果不用前缀和的话就需要双重递归一个递归枚举起点一个递归计算路径总和。本题使用这种思路枚举起点计算路径总和。根节点-1因为枚举数组中所有的元素叶子节点路径和 target 或者 走到最后一个节点子节点当前元素之后的所有元素class Solution { public: bool canPartition(vectorint nums) { int sum 0; for(auto num : nums){ sum num; } if(sum % 2 1) return 0; int n nums.size(); int target sum / 2; bool ans 0; int path 0; auto dfs [](this auto dfs, int cur) - void { if(ans 1) return; if(path target) return; if(path target){ ans 1; return; } if(cur n) return; for(int nxt cur 1; nxt n; nxt){ path nums[nxt]; dfs(nxt); path - nums[nxt]; if(ans) break; } }; dfs(-1); return ans; } };4.2 记忆化根节点-1因为枚举数组中所有的元素叶子节点路径和 target 或者 走到最后一个节点子节点当前元素之后的所有元素记忆从当前节点开始这个路径是否走过class Solution { public: bool canPartition(vectorint nums) { int sum 0; for(auto num : nums){ sum num; } if(sum % 2 1) return 0; int n nums.size(); int target sum / 2; bool ans 0; int path 0; vectorunordered_mapint, bool mem(n 1); auto dfs [](this auto dfs, int cur) - void { if(ans 1) return; if(path target) return; if(path target){ ans 1; return; } if(cur n) return; if(mem[cur 1].count(path)) return; mem[cur 1][path] 1; for(int nxt cur 1; nxt n; nxt){ path nums[nxt]; dfs(nxt); path - nums[nxt]; if(ans) break; } }; dfs(-1); return ans; } };5. 32.最长有效括号给你一个只包含(和)的字符串找出最长有效格式正确且连续括号 子串 的长度。左右括号匹配即每个左括号都有对应的右括号将其闭合的字符串是格式正确的比如(()())。5.1 双重循环思路是枚举每个起点找到每个起点的最长有效括号但是用递归完全没必要因为每个节点只有一个子节点那就是自己后方的元素也可用使用双重循环。class Solution { public: int longestValidParentheses(string s) { int n s.size(); int ans 0; vectorint mem(n, -1); // 记忆化数组mem[i]表示从位置i开始的最长有效括号长度 // 递归函数 auto dfs [](this auto dfs, int start) - int { if (start n) return 0; // 超出边界 if (mem[start] ! -1) return mem[start]; // 已计算过 int balance 0; int maxLen 0; // 从start开始往后找有效括号 for (int i start; i n; i) { if (s[i] () balance; else balance--; if (balance 0) break; // 无效 if (balance 0) { int len i - start 1; maxLen max(maxLen, len); } } // 递归计算从start1开始的结果 int nextResult dfs(start 1); // 取最大值要么从start开始的有效长度要么从start1开始的结果 mem[start] max(maxLen, nextResult); ans max(ans, mem[start]); return mem[start]; }; dfs(0); return ans; } };class Solution { public: int longestValidParentheses(string s) { int n s.size(); int ans 0; // 枚举每个起点 for (int start 0; start n; start) { int balance 0; // 括号平衡计数器 int maxLen 0; // 从start开始的最长有效括号长度 // 从起点开始往后找有效括号 for (int i start; i n; i) { if (s[i] () { balance; } else { balance--; } if (balance 0) { break; // 右括号太多无效 } if (balance 0) { int len i - start 1; maxLen max(maxLen, len); } } ans max(ans, maxLen); } return ans; } };5.2 栈栈里存的不是括号而是下标栈底永远保存着最后一个无效位置的下标遇到(就把它下标入栈遇到)就出栈然后如果栈空了说明这个)是无效的因为没有弹出对应的 (弹出的是无效位置的下标这时不用更新 ans把它下标入栈作为新的边界如果栈不空说明弹出的是有效的 (用当前下标 - 栈顶也就是无效位置下标​ 计算有效长度class Solution { public: int longestValidParentheses(string s) { int n s.size(); stackint st; st.push(-1); // 初始边界 int ans 0; for(int i 0; i n; i){ if(s[i] (){ st.push(i); }else{ st.pop(); if(st.empty()){ st.push(i); }else{ int idx st.top(); ans max(ans, i - idx); } } } return ans; } };