【动态规划】子数组系列

这篇具有很好参考价值的文章主要介绍了【动态规划】子数组系列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

动态规划(子数组系列)

1. 最大子数组和

题目链接

  1. 状态表示

    dp[i]表示到 i 位置时所有子数组的最大和

    如下展示的这样:

    【动态规划】子数组系列,动态规划,算法

  2. 状态转移方程

    【动态规划】子数组系列,动态规划,算法

  3. 初始化

    为了方便初始化,采用虚拟节点的方式,这里初始化dp[0] = 0

  4. 填表

    从左到右

  5. 返回值

    由于每个dp表里的每个值都表示到这个位置的最大子数组的和,所有需要返回最大值

AC代码:文章来源地址https://www.toymoban.com/news/detail-664430.html

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

2. 环形子数组的最大和

题目链接

分析题目:这道题目可以取环形数组,是不是可以像之间做的环形的打家劫舍题目一样来解决?

还是分为两种情况来考虑:

【动态规划】子数组系列,动态规划,算法

如果最大和是蓝色区域的部分,只需要求出最大子数组的和就可以

【动态规划】子数组系列,动态规划,算法

如果是这样,由于数组整体的和是固定的,只需要求出中间的最小值然后相减即可

  1. 状态表示

    讲过前面的题目分析,发现这个题目需要两个状态表示:

    f[i]表示到 i 位置时所有子数组,子数组和最大的值

    g[i]表示到 i 位置时所有子数组,子数组和最小的值

  2. 状态转移方程

    【动态规划】子数组系列,动态规划,算法

  3. 初始化

    采用虚拟节点的方式

  4. 填表

  5. 返回值

    返回两种情况的较大值

AC代码:

class Solution 
{
public:
    const int N = 0x3f3f3f3f;
    int maxSubarraySumCircular(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);
        int fMax = -N, gMin = N, sum = 0;
        for (int i = 1; i <= n; i++)
        {
            f[i] = max(nums[i - 1], f[i - 1] + nums[i - 1]);
            fMax = max(fMax, f[i]);
            g[i] = min(nums[i - 1], g[i - 1] + nums[i - 1]);
            gMin = min(gMin, g[i]);
            sum += nums[i - 1];
        }
        if (sum == gMin) return fMax;
        else return max(fMax, (sum - gMin));
    }
};

3. 乘积最大子数组

题目链接

  1. 状态表示

    f[i]表示以 i 为结尾所有子数组中最大乘积

    g[i]表示以 i 为结尾所有子数组中最小乘积

  2. 状态转移方程

    【动态规划】子数组系列,动态规划,算法

  3. 初始化

    虚拟节点的方式,为了不影响后续的填表采用f[0] = 1, g[0] = 1

  4. 填表

    从左到右

  5. 返回值

    返回乘积最大的即可

AC代码:

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

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

题目链接

  1. 状态表示

    f[i]表示:以 i 位置为结尾所有子数组中乘积为正数的最大长度

    g[i]表示:以 i 位置为结尾所有子数组中乘积为负数的最大长度

  2. 状态转移方程

    【动态规划】子数组系列,动态规划,算法

  3. 初始化

    f[0] = 1, g[0] = 0

  4. 填表

  5. 返回值

    返回乘积为正的最大长度

AC代码:

class Solution 
{
public:
    int getMaxLen(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);
        int ret = -0x3f3f3f3f;
        for (int i = 1; i <= n; i++)
        {
            if (nums[i - 1] > 0)
            {
                f[i] = max(1, f[i - 1] + 1);
                g[i] = max(0, g[i - 1] == 0 ? 0 : g[i - 1] + 1);
            }
            if (nums[i - 1] < 0)
            {
                f[i] = max(0, g[i - 1] == 0 ? 0 : g[i - 1] + 1);
                g[i] = max(1, f[i - 1] + 1);
            }
            ret = max(ret, f[i]);
        }
        return ret;
    }
};

5. 等差数列划分

题目链接

  1. 状态表示

    dp[i]表示到 i 位置时,所有是等差数列子数组之和

  2. 状态转移方程

【动态规划】子数组系列,动态规划,算法3. 初始化 为了防止后续的填表不越界dp[0] = 0, dp[1] = 0
4. 填表

从左到右
5. 返回值

dp表的所有元素之和

AC代码:

class Solution 
{
public:
    int numberOfArithmeticSlices(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> dp(n);
        int sum = 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;
            }
            sum += dp[i];
        }
        return sum;
    }
};

6. 最长湍流子数组

题目链接

  1. 状态表示

    f[i] 以 i 位置为结尾的所有子数组当中,最后呈现“上升” 状态下最长湍流子数组的长度

    g[i] 以 i 位置为结尾的所有子数组当中,最后呈现“下降”状态下最长湍流子数组的长度

  2. 状态转移方程

    【动态规划】子数组系列,动态规划,算法

  3. 初始化

    表里的数据都初始化为1

  4. 填表

    从左到右

  5. 返回值

    返回两个表的最大值

AC代码:

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] > arr[i - 1]) f[i] = g[i - 1] + 1;
            else if (arr[i] < arr[i - 1]) g[i] = f[i - 1] + 1;
            ret = max(ret, max(f[i], g[i]));
        }
        return ret;
    }
};

7. 单词拆分

题目链接

  1. 状态表示

    dp[i] 表示0到i之间的字符串能否被字典拼接

  2. 状态转移方程

    【动态规划】子数组系列,动态规划,算法

  3. 初始化

    可以在字符串s前面加上一个占位符这样就可以没有下标的映射关系

  4. 填表

    从左到右

  5. 返回值

AC代码:

class Solution 
{
public:
    bool wordBreak(string s, vector<string>& wordDict) 
    {
        unordered_set<string> hash;
        for (auto e : wordDict) hash.insert(e);
        int n = s.size();
        vector<bool> dp(n + 1);
        dp[0] = true;
        s = ' ' + s;
        for (int i = 1; i <= n; 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[n];
    }
};

8. 环形字符串中的唯一的子字符串

题目链接

  1. 状态表示

    dp[i]表示到 i 位置的所有子串当中有多少个在base中出现过

  2. 状态转移方程

    【动态规划】子数组系列,动态规划,算法

  3. 初始化

    初始化为1

  4. 填表

  5. 返回值

    由于dp表当中存的值可能是重复的,所以需要进行去重操作。相同字符串结尾的dp值,取最大的值即可

AC代码:

class Solution 
{
public:
    int findSubstringInWraproundString(string s) 
    {
        int n = s.size();
        vector<int> dp(n, 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;
            }
        }
        int hash[26] = {0};
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);
        }
        for (auto x : hash) sum += x;
        return sum;
    }
};

到了这里,关于【动态规划】子数组系列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 动态规划课堂4-----子数组系列

    目录 引入: 例题1:最大子数组和 例题2:环形子数组的最大和 例题3:乘积最大子数组 例题4:乘积为正数的最长子数组 总结: 结语: 在动态规划(DP)子数组系列中,我们还是用前面几节所用的 解题思路1. 状态表示,2.状态转移方程,3.初始化,4.填表顺序,5.返回值 。在

    2024年03月11日
    浏览(35)
  • 【动态规划系列】子数组的最大和

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月03日
    浏览(40)
  • 【动态规划系列】环形子数组的和-918

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月03日
    浏览(54)
  • 3.数组算法、动态规划

    Array是一个容器,可以容纳固定数量的项目,这些项目应该是相同的类型。大多数数据结构都使用数组来实现其算法。以下是理解Array概念的重要术语。 元素 - 存储在数组中的每个项称为元素。 索引 - 数组中元素的每个位置都有一个数字索引,用于标识元素。 可以使用不同语

    2024年02月16日
    浏览(37)
  • C++算法 —— 动态规划(7)两个数组的dp

    每一种算法都最好看完第一篇再去找要看的博客,因为这样会帮你梳理好思路,看接下来的博客也就更轻松了。当然,我也会尽量在写每一篇时都可以不懂这个算法的人也能边看边理解。 动规的思路有五个步骤,且最好画图来理解细节,不要怕麻烦。当你开始画图,仔细阅读

    2024年02月07日
    浏览(52)
  • 【动态规划】【数学】【C++算法】805 数组的均值分割

    视频算法专题 动态规划汇总 数学 给定你一个整数数组 nums 我们要将 nums 数组中的每个元素移动到 A 数组 或者 B 数组中,使得 A 数组和 B 数组不为空,并且 average(A) == average(B) 。 如果可以完成则返回true , 否则返回 false 。 注意:对于数组 arr , average(arr) 是 arr 的所有元素的和

    2024年02月20日
    浏览(42)
  • 60题学会动态规划系列:动态规划算法第三讲

    简单多状态问题 文章目录 一.按摩师 二.打家劫舍系列 三.删除并获得点数 四.粉刷房子 力扣链接:力扣 一个有名的按摩师会收到源源不断的预约请求,每个预约都可以选择接或不接。在每次预约服务之间要有休息时间,因此她不能接受相邻的预约。给定一个预约请求序列,

    2024年02月08日
    浏览(48)
  • 60题学会动态规划系列:动态规划算法第二讲

    都是路径问题~ 文章目录 1.不同路径 2.不同路径II 3.礼物的最大价值 4.下降路径最小和 5.最小路径和 力扣链接:力扣 一个机器人位于一个  m x n   网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在

    2024年02月07日
    浏览(59)
  • 60题学会动态规划系列:动态规划算法第四讲

    买卖股票相关的动态规划题目 文章目录 1. 买卖股票的最佳时机含冷冻期 2. 买卖股票的最佳时期含⼿续费 3. 买卖股票的最佳时机III 4. 买卖股票的最佳时机IV 力扣链接:力扣 给定一个整数数组 prices ,其中第    prices[i]  表示第  i  天的股票价格 。​ 设计一个算法计算出最

    2024年02月13日
    浏览(34)
  • 60题学会动态规划系列:动态规划算法第五讲

    子数组系列题目 文章目录 1.最大子数组和 2.环形子数组的最大和 3.乘积最大数组 4.乘积为正数的最长子数组长度 5.等差数列划分 6.最长湍流子数组 7.单词拆分 8.环绕字符串中唯一的子字符串 力扣链接:力扣 给你一个整数数组  nums  ,请你找出一个具有最大和的连续子数组(

    2024年02月15日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包