【动态规划精选题目】4、子数组系列
此动态规划系列主要讲解大约10个系列【后续持续更新】
本篇讲解子数组系列模型中的8道经典题,会在讲解题目同时给出AC代码
目录
1、力扣53:最大子数组和
?
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n + 1);//多开一个给虚拟节点
int maxs = INT_MIN;
for (int i = 1; i <= n; i++)
{
dp[i] = max(nums[i - 1], dp[i - 1] + nums[i - 1]);
maxs = max(dp[i], maxs);
}
return maxs;
}
};
2、环形子数组的最大和
?本题与[最大子数组和]区别在于,不仅要考虑[数组内的连续区域],还要考虑[数组首尾相连]的一部分
class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
int n = nums.size();
vector<int> f(n + 1), g(n + 1);//因为加了一个虚拟节点,所以开n+1个
int fmax = INT_MIN, gmin = INT_MAX, sum = 0;
for (int i = 1; i <= n; i++)
{
int x = nums[i - 1];
f[i] = max(x, f[i - 1] + x);
fmax = max(fmax, f[i]);
g[i] = min(x, g[i - 1] + x);
gmin = min(gmin, g[i]);
sum += x;
}
return sum == gmin ? fmax : max(fmax, sum - gmin);
}
};
3、力扣152:乘积最大子数组
这道题与「最大子数组和」很相似,可以效仿着定义一下状态表示以及状态转移:
①、dp[i] 表示以?i 为结尾的所有子数组的最大乘积②、则dp[i] = max(nums[i], dp[i - 1] * nums[i]) ;
由于正负号的存在,我们可以看出,这样求 dp[i] 的值是不正确的。因为?dp[i - 1] 的信息并不能让我们得到dp[i]的正确值。比如数组?[-2, 5, -2] ,用上述状态转移得到的dp数组为?[-2, 5, -2] ,最大乘积为?5 。但是实际上的最大乘积应该是所有数相乘,结果为?20 。
究其原因,就是因为我们在求 dp[2] 的时候,因为?nums[2] 是一个负数,因此我们需要的是
「?i - 1 位置结尾的最小的乘积 (-10) 」,这样一个负数乘以「最小值」,才会得到真实的
最大值。
因此,我们不仅需要一个「乘积最大值的 dp 表」,还需要一个「乘积最小值的?dp 表」。
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
vector<int> f(n + 1), g(n + 1);
f[0] = 1, g[0] = 1;
int ret = INT_MIN;
for (int i = 1; i <= n; i++)
{
int x = nums[i - 1], y = f[i - 1] * nums[i - 1], z = g[i - 1]
* nums[i - 1];
f[i] = max(x, max(y, z));
g[i] = min(x, min(y, z));
ret = max(ret, f[i]);
}
return ret;
}
};
?4、乘积为正数的最长子数组长度
继续效仿「最大子数组和」中的状态表示,尝试解决这个问题。
状态表示: dp[i] 表示「所有以i结尾的子数组,乘积为正数的最?子数组的?度」。
思考状态转移:对于?i 位置上的 nums[i] ,我们可以分三种情况讨论:
①. 如果nums[i] = 0 ,那么所有以i 为结尾的子数组的乘积都不可能是正数,此时dp[i] = 0 ;
②. 如果nums[i] > 0 ,那么直接找到dp[i - 1] 的值,然后加一即可,此时dp[i] = dp[i - 1] + 1 ;
③. 如果nums[i] < 0 ,因为在现有的条件下,你根本没办法得到此时的最??度。单单靠一个?dp[i - 1] ,我们无法推导出dp[i]的值。但是,但乘法是存在「负负得正」的。如果我们知道「以?i - 1 为结尾的所有子数组,乘积为负数的最?子数组的?度」neg[i - 1] ,那么此时的dp[i]是不是就等于neg[i - 1] + 1呢?通过上面的分析,我们可以得出,需要两个dp 表,才能推导出最终的结果。不仅需要一个「乘积
为正数的最?子数组」,还需要一个「乘积为负数的最?子数组」。
①、为什么要推出g表的状态转移方程?因为f表用到了g表?
②、下面再详细讲解一下虚拟节点
class Solution {
public:
int getMaxLen(vector<int>& nums) {
int n = nums.size();
vector<int> f(n + 1), g(n + 1);
int ret = INT_MIN;
for (int i = 1; i <= n; i++)
{//如果nums[i-1]为0,那f[i]和g[i]均为0,又因为vector已经初始化为0
//所以我们不用管了
if (nums[i - 1] > 0)
{
f[i] = f[i - 1] + 1;
g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
}
else if (nums[i - 1] < 0)
{
f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
g[i] = f[i - 1] + 1;
}
ret = max(ret, f[i]);
}
return ret;
}
};
5、力扣413:等差数列划分
1、状态表示:
由于我们的研究对象是「一段连续的区间」,如果我们状态表示定义成?[0, i] 区间内一共有多少等差数列,那么我们在分析dp[i] 的状态转移时,会无从下手,因为我们不清楚前面那么多的「等差数列都在什么位置」。所以说,我们定义的状态表示必须让等差数列「有迹可循」,让状态转移的时候能找到「大部队」。因此,我们可以「固定死等差数列的结尾」,定义下面的状态表示:
dp[i] 表示必须「以i 位置的元素为结尾」的等差数列有多少种。
补充:上面求的是以b结尾的等差数列的个数,是因为此时加上c还能构成等差数列
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n);
int ret = 0;
for (int i = 2; i < n; i++)
{
dp[i] = nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2] ? dp[i - 1] + 1 : 0;
ret += dp[i];
}
return ret;
}
};
6、最大湍(tuan)流子数组
?题目分析:
我们先尝试定义状态表示为:
dp[i] 表示「以i位置为结尾的最?湍流数组的?度」。
但是问题来了,如果状态表示这样定义的话,以?i 位置为结尾的最?湍流数组的?度我们没法从之前的状态推导出来。因为我们不知道前一个最?湍流数组的结尾处是递增的,还是递减的。因此,我们需要状态表示能表示多一点的信息:要能让我们知道这一个最?湍流数组的结尾是「递增」的还是「递减」的。
因此需要两个?dp 表
class Solution {
public:
int maxTurbulenceSize(vector<int>& arr) {
int n = arr.size();
vector<int> f(n, 1), g(n, 1);
int ret = 1;
for (int i = 1; i < n; i++)
{
if (arr[i - 1] < arr[i]) f[i] = g[i - 1] + 1;
if (arr[i - 1] > arr[i]) g[i] = f[i - 1] + 1;
ret = max(ret, max(g[i], f[i]));
}
return ret;
}
};
7、单词拆分
状态转移方程:
对于dp[i] ,为了确定当前的字符串能否由字典里面的单词构成,根据最后一个单词的起始位
置?j ,我们可以将其分解为前后两部分:
①. 前面一部分[0, j - 1] 区间的字符串;
②. 后面一部分[j, i] 区间的字符串。
其中前面部分我们可以在?dp[j - 1] 中找到答案,后面部分的子串可以在字典里面找到。
因此,我们得出一个结论:当我们在从?0 ~ i 枚举?j 的时候,只要?dp[j - 1] = true?
并且后面部分的子串?s.substr(j, i - j + 1) 能够在字典中找到,那么?dp[i] = true 。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
//哈希表优化的小细节:
//在状态转移中,我们需要判断后面部分的子串「是否在字典」之中,因此会「频繁的用到查询操
//作」,为了节省效率,我们可以提前把「字典中的单词」存入到「哈希表」中。
unordered_set<string> hash;
for (auto& s : wordDict) hash.insert(s);
int n = s.size();
vector<bool> dp(n + 1);//多开一个给虚拟节点
dp[0] = true;//虚拟节点初始化,便于后续填表正确
s = " " + s;//使原始字符串下标+1,与dp表对应,注:加什么字符都可以
for (int i = 1; i <= n; i++)//填dp表
{
//遍历最后一个单词的起始位置,范围[1,i]
//因为你让原始字符串多加了一个字符
for (int j = i; j >= 1; j--)
{
if (dp[j - 1] && hash.count(s.substr(j, i - j + 1)))
{
dp[i] = true;
break;//此时以j位置起始的单词判断完毕才会break
}
}
}
return dp[n];
}
};
?补充:
string的substr(字符截取函数):
?unordered_set中的count函数:
cout(x):若x元素在容器中返回1,否则返回0
8、环绕字符串中唯一的子字符串
?示例分析:
3、初始化
dp表中所有的值初始化为1即可【根据实际情况初始化的,其次是这么做状态转移方程直接写为dp[i] += dp[i - 1]即可】
4、填表顺序
从左往右填即可
class Solution {
public:
int findSubstringInWraproundString(string s) {
int n = s.size();
vector<int> dp(n, 1);//根据实际,初始化为1
for (int i = 1; i < n; i++)
{
if (s[i - 1] + 1 == s[i] || (s[i - 1] == 'z' && s[i] == 'a'))
dp[i] += dp[i - 1];//因为初始化为1,所以这里直接+=dp[i-1]
}
//哈希表映射小写字母a~z,找出以每个字符结尾的最大dp值即可
int hash[26] = {0};
for(int i = 0; i < n; i++)
{
//a会映射为0,b映射为1,c映射为2...
//算出以每个字符结尾的最大dp值,
hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);
}
int ret = 0;
for (auto& e : hash) ret += e;
return ret;
}
};
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!