动态规划核心：数组问题实战

简介

「DP 中的数组问题」是动态规划最核心、最高频的应用场景之一 —— 这类问题以一维 / 二维数组为载体，通过定义 “以数组下标为核心的状态”，解决 “子数组 / 子序列 / 区间” 相关的最优解 / 计数问题。

最大子数组和

53. 最大子数组和 – 力扣（LeetCode）

题意：找到一块连续的最大子数组和

暴力枚举：枚举每一个子数组，对比和，找到最大的

动态规划：

dp[i]：表示以i位置结尾的最大子数组和

那么dp[i]的求解就是看当前位置nums[i]   和   前面的dp[i-1]+nums[i]哪个大

你的dp[i-1]就表示了以i-1位置结尾的最大子数组和，所以要连续的话就是+nums[i]

所以本质就是比较这两的大小

返回值：注意不是返回最后一个位置，返回最后一个位置是表示以m位置结尾的最大

应该返回dp表当中最大的

class Solution {
public:
int maxSubArray(vector<int>& nums) {
int m=nums.size();
int ret=nums[0];
vector<int>dp(m);
dp[0]=nums[0];
for(int i=1;i<m;i++){
dp[i]=max(dp[i-1]+nums[i],nums[i]);
ret=max(ret,dp[i]);
}
return ret;
}
};

环形子数组的最大和

918. 环形子数组的最大和 – 力扣（LeetCode）

本题的题意相比第一道就是多了个环形，前面和后面可以连起来

我们需要想办法转换成第一题

可以想象一下，最大和可能是整个数组的中间一部分，也可能是前面和后面的一部分

第二种就是找个最小，然后sum-min即可

返回值有个特殊情况，就是数组全部为负数的时候

class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
int m = nums.size();
if (m == 1) {
return nums[0];
}
int ret = nums[0];
int ret1 = nums[0];
int sum = nums[0];
vector<int> dp(m), dp1(m);
dp[0] = nums[0];
dp1[0] = nums[0];
for (int i = 1; i < m; i++) {
sum += nums[i];
dp[i] = max(dp[i – 1] + nums[i], nums[i]);
dp1[i] = min(dp1[i – 1] + nums[i], nums[i]);
ret = max(ret, dp[i]);
ret1 = min(ret1, dp1[i]);
}
if(sum==ret1){
return ret;
}
return max(ret, sum – ret1);
}
};

乘积最大子数组

152. 乘积最大子数组 – 力扣（LeetCode）

这道题和最大子数组和非常相似

根据经验+题目要求

dp[i]:表示以i位置结尾的乘积最大子数组

但是分析的时候发现，以i位置为结尾的子数组有长度为1和长度>1的

当长度为1，那就是nums[i]本身

当长度>1的时候，如果nums[i]>0，那此时是nums[i]*dp[i-1]

如果nums[i]<0，那此时就不能是nums[i]*dp[i-1]了，因为你是负数乘dp[i-1]会出现别的情况

dp[i-1]可能是正的也可能是负的，导致nums[i]×的时候会出现最大或最小

乘法的特性（负负得正）导致 “当前的最小乘积” 可能在乘以一个负数后，变成 “最大乘积”

所以要分为f[i]和g[i]，一个统计最大，一个统计最小

class Solution {
public:
int maxProduct(vector<int>& nums) {
int m=nums.size();
vector<int> f(m),g(m);
int ret=nums[0];
f[0]=nums[0];
g[0]=nums[0];
for(int i=1;i<m;i++){
f[i]=max(max(nums[i],nums[i]*f[i-1]),nums[i]*g[i-1]);
g[i]=min(min(nums[i],nums[i]*f[i-1]),nums[i]*g[i-1]);
ret=max(f[i],ret);
}
return ret;
}
};

乘积为正数的最长子数组长度

1567. 乘积为正数的最长子数组长度 – 力扣（LeetCode）

当nums[i]==0的时候不需要考虑，直接让dp表的值为0即可，因为为0是凑不出来最大的最小

class Solution {
public:
int getMaxLen(vector<int>& nums) {
int m = nums.size();
vector<int> f(m + 1), g(m + 1); // 前面添加一个空结点
int ret = 0;
for (int i = 1; i < m + 1; i++) {
if (nums[i-1] > 0) {
f[i] = f[i – 1] + 1;
g[i] = g[i – 1] == 0 ? 0 : g[i – 1] + 1;
}
if(nums[i-1]<0){
f[i] = g[i – 1] == 0 ? 0 : g[i – 1] + 1;
g[i] = f[i – 1] + 1;
}
ret = max(f[i], ret);
}
return ret;
}
};

等差数列划分

413. 等差数列划分 – 力扣（LeetCode）

先考虑是否一个状态能够推出状态转移方程

dp[i]:表示以i位置结尾的所有等差数列的个数

注意等差数列有个性质，多加一个数如果符合等差数列，只要跟子数组的最后两个数是否符合等差数列即可

即[a,b,c,d] 一开始是等差数列，再加上一个e，是否构成等差数列，仅仅需要看c d e是否等差

class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
int m=nums.size();
int ret=0;
vector<int> dp(m);
for(int i=2;i<m;i++){
dp[i]=nums[i]-nums[i-1]==nums[i-1]-nums[i-2]?dp[i-1]+1:0;
ret+=dp[i];
}
return ret;
}
};
class Solution {
public:
int maxTurbulenceSize(vector<int>& arr) {
int m = arr.size();
if (m == 2) {
if (arr[0] == arr[1]) {
return 1;
}
return m;
}
if(m==1){
return 1;
}
vector<int> dp(m);
dp[0] = 1;
dp[1] = 2;
int ret = 0;
for (int i = 2; i < m; i++) {
if ((arr[i] > arr[i – 1] && arr[i – 2] > arr[i – 1]) ||
(arr[i] < arr[i – 1] && arr[i – 2] < arr[i – 1])) {
dp[i] = dp[i – 1] + 1;
} else {
if (arr[i] == arr[i – 1]) {
dp[i] = 1;
} else {
dp[i] = 2;
}
}
ret = max(ret, dp[i]);
}
return ret;
}
};

最长端流子数组

978. 最长湍流子数组 – 力扣（LeetCode）

解法一

题目可以想象成一个上升和下降趋势的折线图，当后一个数比前一个数大时就是上升

这样端流数组就是一上一下一上一下

这道题和等差数列划分有点像，只不过一个是验证等差，一个是验证端流

那就可以照搬dp[i]：表示以i位置结尾的最长端流子数组

那dp[i]的位置填写：

如果arr[i]>arr[i-1]的，我们无法根据i和i-1的大小判断端流，此时还要根据i-2的大小

这就跟等差判断一样，如果[a，b，c，d]已经是端流了，新增加的e要和c，d比较即可

所以

当符合这个条件是dp[i]=dp[i-1]+1

此时其他情况也有特殊，有三种不像端流一样一下上升一下下降的折线图

当原来已经呈现上升趋势，来了一个新的还是上升，那此时最长为2，要和前面的组合在一起

当原来是下降趋势，来了一个新的还是下降，此时最长为2，要和前面的组合在一起

当新的arr[i]==arr[i-1]时，此时最长为1，不能和前面的组合在一起

本质就是将等差的规则转换成端流的规则而已

class Solution {
public:
int maxTurbulenceSize(vector<int>& arr) {
int m = arr.size();
if (m == 2) {
if (arr[0] == arr[1]) {
return 1;
}
return m;
}
if(m==1){
return 1;
}
vector<int> dp(m);
dp[0] = 1;
dp[1] = 2;
int ret = 0;
for (int i = 2; i < m; i++) {
if ((arr[i] > arr[i – 1] && arr[i – 2] > arr[i – 1]) ||
(arr[i] < arr[i – 1] && arr[i – 2] < arr[i – 1])) {
dp[i] = dp[i – 1] + 1;
} else {
if (arr[i] == arr[i – 1]) {
dp[i] = 1;
} else {
dp[i] = 2;
}
}
ret = max(ret, dp[i]);
}
return ret;
}
};

解法二

如果你发现一个状态无法表示时，也就是dp[i]，无法反映出前面的上升还是下降趋势

那么可以新增加状态表示，两个，一个是最后呈现上升状态下的最长，一个是呈现下降状态下的最长

初始化经过前面的讲解有三种

1：添加虚拟节点，但是要注意下标映射关系

2：直接把会越界的地方提前填表

3：根据实际情况去初始化，这里就是这样

因为最小的子数组必然是1，只需要把dp表初始化为1即可，并且这样很多地方填1的地方都少了判断

两个解法本质一样的，第二个是把状态拆分出来

一般来说dp先想一个状态，如果一个状态表示不了，你可以新增加

单词拆分

139. 单词拆分 – 力扣（LeetCode）

按照正常的经验+题目要求定义状态

不是认为所有的dp都是O(n)，时间复杂度是以状态数*状态转移来看的

这道题就是O(n^2)，每填写一个位置要想遍历

这里的初始化当中：加了虚拟节点，避免j-1的时候越界，当j==0的时候，此时是代表整个长度了，那为了进入if语句，你需要把dp[0]=true，这样j==1时，j-1代表整个长度时可以进入if语句

并且这里下标映射可以在s的前面加一个特殊字符，因为字符串的切割很麻烦，防止出现切割错误

class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> hash;
for (auto e : wordDict) {
hash.insert(e);
}
int m = s.size();
if (m == 0) {
return true;
}
vector<bool> dp(m + 1);
dp[0] = true;
s = ' ' + s;
for (int i = 1; i <= m; i++) {
for (int j = i; j >= 1; j–) {
if (dp[j – 1] && hash.count(s.substr(j, i – j + 1))) {
dp[i] = true;
break;
}
}
}
return dp[m];
}
};

环绕字符串中唯一的子字符串

467. 环绕字符串中唯一的子字符串 – 力扣（LeetCode）

题意：有一个模式串a-za-za-z

给一个匹配串，需要找到所有不重复的匹配的子串

因为初始化的时候把所有dp表当中所有的值都初始化为1了，所以dp[i]+=dp[i-1]即可

但是这里没有去重，假设你有重复的相同的字符为结尾

比如都是cdef  abcdef，当你计算的时候以f为结尾就会出现相同子串，我们仅仅需要统计最大的那个的即可

这时候我们需要对dp[i]中去重，把所有相同字符结尾的dp[i]大的统计即可，我们可以利用hash，把大的存进去即可，然后统计一下hash即可

class Solution {
public:
int findSubstringInWraproundString(string s) {
int m = s.size();
if (m == 1) {
return 1;
}
int hash[26] = {0};
hash[s[0] – 'a'] = 1;
vector<int> dp(m, 1);
for (int i = 1; i < m; i++) {
if ((s[i] – 1 == s[i – 1]) || (s[i] == 'a' && s[i – 1] == 'z')) {
dp[i] += dp[i – 1];
}
if (dp[i] > hash[s[i] – 97]) {
hash[s[i] – 97] = dp[i];
}
}
int ret = 0;
for (int i = 0; i < 26; i++) {
ret += hash[i];
}
return ret;
}
};

总结

以上的题都是连续的子数组，因为连续，注定了以i位置结尾的必定是和i-1位置有练习

因为 “连续” 意味着当前子数组的解只能从 “以 i-1 结尾的子数组” 延伸而来，或重新以 i 开头。

核心逻辑：当前状态 = （前一个状态延伸） or （重新开始）

• 延伸：如果 nums [i] 能接在以 i-1 结尾的子数组后，dp[i] = dp[i-1] + 增量（增量可能是 1、nums [i]、乘积等）；
• 重新开始：如果不能延伸，dp[i] = 初始值（通常是 nums [i]、1、false 等）。

• 核心锚点：子数组 DP 的状态定义必为「以 i 结尾的 XXX」，利用 “连续” 特性仅依赖 i-1 的状态；
• 转移逻辑：要么从 i-1 延伸（连续），要么重新以 i 开头（不连续）；
• 高频分支：
  • 最值类：单状态（和）/ 双状态（乘积）；
  • 计数类：前缀和 + 哈希（避免 O (n²)）；
  • 合法性：枚举拆分点（单词拆分）/ 区间 DP（回文）；

碰到这类子数组问题，只需要定义以i-1结尾即可