【动态规划精选题目】4、子数组系列

2024-01-03 18:46:43

此动态规划系列主要讲解大约10个系列【后续持续更新】

本篇讲解子数组系列模型中的8道经典题,会在讲解题目同时给出AC代码

目录

1、力扣53:最大子数组和

2、环形子数组的最大和

3、力扣152:乘积最大子数组

?4、乘积为正数的最长子数组长度

5、力扣413:等差数列划分

6、最大湍(tuan)流子数组

7、单词拆分

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


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;
    }
};

文章来源:https://blog.csdn.net/m0_74044018/article/details/135309667
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。