1. 动态规划解决子数组问题的核心思路动态规划是解决子数组系列问题的利器其核心在于定义合适的状态表示和状态转移方程。对于子数组问题我们通常定义dp[i]为以第i个元素结尾的子数组的某种特性这种定义方式能够很好地捕捉子数组的连续性特征。以最大子数组和问题为例dp[i]表示以nums[i]结尾的子数组的最大和。这种定义的精妙之处在于保证了子数组的连续性 - 必须以nums[i]结尾通过状态转移可以利用前一个状态的结果 - dp[i]可以从dp[i-1]推导而来最终结果是所有dp[i]中的最大值 - 因为最优解可能出现在任意位置关键提示子数组问题中定义以i结尾的状态是通用套路这保证了子数组的连续性要求。2. 基础问题最大子数组和2.1 问题描述与解法给定整数数组nums找出具有最大和的连续子数组返回其最大和。解法代码class Solution { public: int maxSubArray(vectorint nums) { int n nums.size(); vectorint dp(n); dp[0] nums[0]; int maxSum dp[0]; for(int i 1; i n; i) { dp[i] max(nums[i], dp[i-1] nums[i]); maxSum max(maxSum, dp[i]); } return maxSum; } };2.2 关键点解析状态定义dp[i]表示以nums[i]结尾的最大子数组和状态转移要么单独以nums[i]作为子数组(dp[i] nums[i])要么将nums[i]接到前一个子数组后面(dp[i] dp[i-1] nums[i])初始化dp[0]必须为nums[0]因为单个元素也是一个子数组空间优化可以用一个变量代替dp数组将空间复杂度降至O(1)2.3 常见错误与修正错误1将dp[i]定义为前i个元素的最大子数组和修正这样定义无法保证子数组的连续性无法正确推导状态转移错误2初始化dp[0]为0修正对于nums [-1]会错误返回0而不是-13. 进阶问题环形子数组的最大和3.1 问题变形与思路当数组首尾相连时最大子数组可能出现在常规情况中间某段连续子数组环形情况首尾两段的和最大此时中间部分的和最小解法思路计算常规最大子数组和max1计算整个数组的和total计算常规最小子数组和min1最终结果为max(max1, total - min1)3.2 实现代码class Solution { public: int maxSubarraySumCircular(vectorint nums) { int n nums.size(); int maxSum nums[0], minSum nums[0]; int curMax 0, curMin 0; int total 0; for(int num : nums) { curMax max(num, curMax num); maxSum max(maxSum, curMax); curMin min(num, curMin num); minSum min(minSum, curMin); total num; } return maxSum 0 ? max(maxSum, total - minSum) : maxSum; } };3.3 边界情况处理全负数数组的特殊处理当maxSum 0时说明所有数都是负数此时total - minSum 0因为minSum total但子数组不能为空所以直接返回maxSum4. 乘积最大子数组问题4.1 问题特性分析与和不同乘积有以下特点负数乘以负数会变正数当前的最小乘积可能在乘以负数后变成最大乘积需要同时维护最大和最小两个dp数组4.2 双DP数组解法class Solution { public: int maxProduct(vectorint nums) { int n nums.size(); vectorint maxDp(n), minDp(n); maxDp[0] minDp[0] nums[0]; int res nums[0]; for(int i 1; i n; i) { maxDp[i] max({nums[i], maxDp[i-1]*nums[i], minDp[i-1]*nums[i]}); minDp[i] min({nums[i], maxDp[i-1]*nums[i], minDp[i-1]*nums[i]}); res max(res, maxDp[i]); } return res; } };4.3 状态转移解释对于每个nums[i]有三种可能自己单独作为子数组与前一个最大乘积子数组相乘与前一个最小乘积子数组相乘负数情况必须同时维护maxDp和minDp因为当前是正数时希望乘以前面的最大乘积当前是负数时希望乘以前面的最小乘积5. 乘积为正数的最长子数组5.1 问题转化思路需要找到乘积为正的最长子数组长度。可以转化为统计正负号的变化情况维护两个dp数组pos[i]以i结尾乘积为正的最长子数组长度neg[i]以i结尾乘积为负的最长子数组长度5.2 具体实现class Solution { public: int getMaxLen(vectorint nums) { int n nums.size(); vectorint pos(n), neg(n); pos[0] nums[0] 0 ? 1 : 0; neg[0] nums[0] 0 ? 1 : 0; int res pos[0]; for(int i 1; i n; i) { if(nums[i] 0) { pos[i] pos[i-1] 1; neg[i] neg[i-1] 0 ? neg[i-1] 1 : 0; } else if(nums[i] 0) { pos[i] neg[i-1] 0 ? neg[i-1] 1 : 0; neg[i] pos[i-1] 1; } else { pos[i] neg[i] 0; } res max(res, pos[i]); } return res; } };5.3 状态转移分析当前数为正数时正数长度1负数长度如果前一个负数长度存在则1否则归零当前数为负数时正数长度前一个负数长度1负负得正负数长度前一个正数长度1当前数为零时正负长度都归零6. 等差数列划分问题6.1 问题定义与解法计算数组中等差子数组的个数。等差子数组指长度≥3的连续子数组且相邻元素差值相同。解法思路dp[i]表示以i结尾的等差子数组个数如果nums[i]-nums[i-1] nums[i-1]-nums[i-2]则dp[i] dp[i-1] 1总数为所有dp[i]的和6.2 实现代码class Solution { public: int numberOfArithmeticSlices(vectorint nums) { int n nums.size(); if(n 3) return 0; vectorint dp(n, 0); int res 0; for(int i 2; i n; i) { if(nums[i] - nums[i-1] nums[i-1] - nums[i-2]) { dp[i] dp[i-1] 1; res dp[i]; } } return res; } };6.3 关键点说明初始化dp[0]dp[1]0因为长度不足3状态转移只有当连续三个数等差时才能形成新的等差子数组结果累计每个dp[i]表示以i结尾的新增等差子数组数7. 湍流子数组问题7.1 问题描述湍流子数组指相邻元素的比较符号在和之间交替。求最长湍流子数组长度。解法思路定义两个dp数组up[i]以i结尾最后是上升的湍流子数组长度down[i]以i结尾最后是下降的湍流子数组长度7.2 实现代码class Solution { public: int maxTurbulenceSize(vectorint nums) { int n nums.size(); if(n 1) return 1; vectorint up(n, 1), down(n, 1); int res 1; for(int i 1; i n; i) { if(nums[i] nums[i-1]) { up[i] down[i-1] 1; down[i] 1; } else if(nums[i] nums[i-1]) { down[i] up[i-1] 1; up[i] 1; } else { up[i] down[i] 1; } res max({res, up[i], down[i]}); } return res; } };7.4 状态转移逻辑nums[i] nums[i-1]上升长度前一个下降长度1下降长度重置为1nums[i] nums[i-1]下降长度前一个上升长度1上升长度重置为1相等时两个长度都重置为18. 单词拆分问题8.1 问题转化思路判断字符串是否能被拆分成字典中的单词。可以转化为dp[i]表示前i个字符能否被拆分dp[i] dp[j] s[j..i]在字典中对于某个j i8.2 实现代码class Solution { public: bool wordBreak(string s, vectorstring wordDict) { unordered_setstring dict(wordDict.begin(), wordDict.end()); int n s.size(); vectorbool dp(n1, false); dp[0] true; for(int i 1; i n; i) { for(int j 0; j i; j) { if(dp[j] dict.count(s.substr(j, i-j))) { dp[i] true; break; } } } return dp[n]; } };8.3 优化技巧字典使用哈希集合存储提高查找效率内层循环可以从i-1倒序遍历找到第一个满足条件的j即可break可以预处理字典中最长单词长度限制内层循环的范围9. 环绕字符串子串问题9.1 问题分析计算字符串s中有多少不同的非空子串是环绕字符串zabc...xyz的子串。解法思路dp[i]表示以s[i]结尾的连续环绕子串长度如果s[i]是s[i-1]的下一个字母考虑z到a的环绕则dp[i] dp[i-1] 1最终结果是各字符结尾的最大dp值之和9.2 实现代码class Solution { public: int findSubstringInWraproundString(string s) { int n s.size(); vectorint dp(n, 1); int count[26] {0}; for(int i 1; i n; i) { if((s[i] - s[i-1] 1) || (s[i-1] z s[i] a)) { dp[i] dp[i-1] 1; } } for(int i 0; i n; i) { int idx s[i] - a; count[idx] max(count[idx], dp[i]); } return accumulate(count, count26, 0); } };9.3 关键点说明环绕关系判断两种特殊情况常规情况s[i] s[i-1]1环绕情况s[i-1]z且s[i]a去重处理对每个字符只记录以其结尾的最长连续子串长度结果计算26个字母对应最大长度的总和10. 动态规划解题通用技巧总结状态定义套路子数组问题通常定义为以i结尾的子数组的某种特性子序列问题通常定义为前i个元素的某种特性状态转移设计考虑当前元素单独成组的情况考虑当前元素与前面组合的情况有时需要维护多个dp数组如最大/最小、正/负初始化技巧通常dp[0]需要特殊处理可以考虑在数组前添加虚拟元素简化边界处理空间优化很多问题只需要前一个状态可以用变量代替数组滚动数组技巧可将空间复杂度从O(n)降到O(1)结果获取可能是dp数组的最后一个值也可能是dp数组中的最大值/最小值有时需要遍历整个dp数组才能得到最终结果在实际刷题过程中建议从简单问题入手逐步理解状态定义和转移的套路然后尝试解决更复杂的问题。对于每道题先思考清楚状态表示和转移方程再动手编码这样可以事半功倍。