1. 动态规划解决子数组问题的核心思路

动态规划是解决子数组系列问题的利器，其核心在于定义合适的状态表示和状态转移方程。对于子数组问题，我们通常定义dp[i]为"以第i个元素结尾的子数组的某种特性"，这种定义方式能够很好地捕捉子数组的连续性特征。

以最大子数组和问题为例，dp[i]表示以nums[i]结尾的子数组的最大和。这种定义的精妙之处在于：

1. 保证了子数组的连续性 - 必须以nums[i]结尾
2. 通过状态转移可以利用前一个状态的结果 - dp[i]可以从dp[i-1]推导而来
3. 最终结果是所有dp[i]中的最大值 - 因为最优解可能出现在任意位置

关键提示：子数组问题中，定义"以i结尾"的状态是通用套路，这保证了子数组的连续性要求。

2. 基础问题：最大子数组和

2.1 问题描述与解法

给定整数数组nums，找出具有最大和的连续子数组，返回其最大和。

解法代码：

class Solution { public: int maxSubArray(vector<int>& nums) { int n = nums.size(); vector<int> 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 关键点解析

1. 状态定义：dp[i]表示以nums[i]结尾的最大子数组和
2. 状态转移：
   • 要么单独以nums[i]作为子数组(dp[i] = nums[i])
   • 要么将nums[i]接到前一个子数组后面(dp[i] = dp[i-1] + nums[i])
3. 初始化：dp[0]必须为nums[0]，因为单个元素也是一个子数组
4. 空间优化：可以用一个变量代替dp数组，将空间复杂度降至O(1)

2.3 常见错误与修正

错误1：将dp[i]定义为前i个元素的最大子数组和

• 修正：这样定义无法保证子数组的连续性，无法正确推导状态转移

错误2：初始化dp[0]为0

• 修正：对于nums = [-1]，会错误返回0而不是-1

3. 进阶问题：环形子数组的最大和

3.1 问题变形与思路

当数组首尾相连时，最大子数组可能出现在：

1. 常规情况：中间某段连续子数组
2. 环形情况：首尾两段的和最大（此时中间部分的和最小）

解法思路：

• 计算常规最大子数组和max1
• 计算整个数组的和total
• 计算常规最小子数组和min1
• 最终结果为max(max1, total - min1)

3.2 实现代码

class Solution { public: int maxSubarraySumCircular(vector<int>& 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）
• 但子数组不能为空，所以直接返回maxSum

4. 乘积最大子数组问题

4.1 问题特性分析

与和不同，乘积有以下特点：

1. 负数乘以负数会变正数
2. 当前的最小乘积可能在乘以负数后变成最大乘积
3. 需要同时维护最大和最小两个dp数组

4.2 双DP数组解法

class Solution { public: int maxProduct(vector<int>& nums) { int n = nums.size(); vector<int> 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]，有三种可能：

1. 自己单独作为子数组
2. 与前一个最大乘积子数组相乘
3. 与前一个最小乘积子数组相乘（负数情况）

必须同时维护maxDp和minDp，因为：

• 当前是正数时，希望乘以前面的最大乘积
• 当前是负数时，希望乘以前面的最小乘积

5. 乘积为正数的最长子数组

5.1 问题转化思路

需要找到乘积为正的最长子数组长度。可以转化为：

• 统计正负号的变化情况
• 维护两个dp数组：
  • pos[i]：以i结尾乘积为正的最长子数组长度
  • neg[i]：以i结尾乘积为负的最长子数组长度

5.2 具体实现

class Solution { public: int getMaxLen(vector<int>& nums) { int n = nums.size(); vector<int> 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，否则归零
2. 当前数为负数时：
   • 正数长度=前一个负数长度+1（负负得正）
   • 负数长度=前一个正数长度+1
3. 当前数为零时：
   • 正负长度都归零

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(vector<int>& nums) { int n = nums.size(); if(n < 3) return 0; vector<int> 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 关键点说明

1. 初始化：dp[0]=dp[1]=0，因为长度不足3
2. 状态转移：只有当连续三个数等差时，才能形成新的等差子数组
3. 结果累计：每个dp[i]表示以i结尾的新增等差子数组数

7. 湍流子数组问题

7.1 问题描述

湍流子数组指相邻元素的比较符号在"<"和">"之间交替。求最长湍流子数组长度。

解法思路：

• 定义两个dp数组：
  • up[i]：以i结尾，最后是上升的湍流子数组长度
  • down[i]：以i结尾，最后是下降的湍流子数组长度

7.2 实现代码

class Solution { public: int maxTurbulenceSize(vector<int>& nums) { int n = nums.size(); if(n == 1) return 1; vector<int> 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 状态转移逻辑

1. nums[i] > nums[i-1]：
   • 上升长度=前一个下降长度+1
   • 下降长度重置为1
2. nums[i] < nums[i-1]：
   • 下降长度=前一个上升长度+1
   • 上升长度重置为1
3. 相等时：
   • 两个长度都重置为1

8. 单词拆分问题

8.1 问题转化思路

判断字符串是否能被拆分成字典中的单词。可以转化为：

• dp[i]表示前i个字符能否被拆分
• dp[i] = dp[j] && s[j..i]在字典中，对于某个j < i

8.2 实现代码

class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> dict(wordDict.begin(), wordDict.end()); int n = s.size(); vector<bool> dp(n+1, 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 优化技巧

1. 字典使用哈希集合存储，提高查找效率
2. 内层循环可以从i-1倒序遍历，找到第一个满足条件的j即可break
3. 可以预处理字典中最长单词长度，限制内层循环的范围

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(); vector<int> 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, count+26, 0); } };

9.3 关键点说明

1. 环绕关系判断：两种特殊情况
   • 常规情况：s[i] == s[i-1]+1
   • 环绕情况：s[i-1]=='z'且s[i]=='a'
2. 去重处理：对每个字符，只记录以其结尾的最长连续子串长度
3. 结果计算：26个字母对应最大长度的总和

10. 动态规划解题通用技巧总结

1. 状态定义套路：

   • 子数组问题：通常定义为"以i结尾的子数组的某种特性"
   • 子序列问题：通常定义为"前i个元素的某种特性"

2. 状态转移设计：

   • 考虑当前元素单独成组的情况
   • 考虑当前元素与前面组合的情况
   • 有时需要维护多个dp数组（如最大/最小、正/负）

3. 初始化技巧：

   • 通常dp[0]需要特殊处理
   • 可以考虑在数组前添加虚拟元素简化边界处理

4. 空间优化：

   • 很多问题只需要前一个状态，可以用变量代替数组
   • 滚动数组技巧可将空间复杂度从O(n)降到O(1)

5. 结果获取：

   • 可能是dp数组的最后一个值
   • 也可能是dp数组中的最大值/最小值
   • 有时需要遍历整个dp数组才能得到最终结果

在实际刷题过程中，建议从简单问题入手，逐步理解状态定义和转移的套路，然后尝试解决更复杂的问题。对于每道题，先思考清楚状态表示和转移方程，再动手编码，这样可以事半功倍。