网络知识 娱乐 牛客网《剑指offer》专栏刷题练习之掌握动态规划思想

牛客网《剑指offer》专栏刷题练习之掌握动态规划思想

✅作者简介:C/C++领域新星创作者,为C++和java奋斗中
✨个人社区:微凉秋意社区
🔥系列专栏:剑指offer精讲
📃推荐一款模拟面试、刷题神器👉注册免费刷题

🔥前言

今天给大家分享算法中的一个重要思想——动态规划。题目源自牛客网的 《剑指offer》 专栏,我将通过两个经理题目来给大家讲清楚动态规划思想,让大家面对这一类题目时有自己的解题思路。

文章目录

  • 一、连续子数组的最大和
    • 1、题目要求
    • 2、个人题解
      • 2.1、解题思路
      • 2.2、代码实现
      • 2.3、代码解析
  • 二、连续子数组的最大和(二)
    • 1、题目要求
    • 2、个人题解
      • 2.1、解题思路
      • 2.2、代码实现
      • 2.3、代码解析
  • 三、动态规划知识学习


一、连续子数组的最大和

1、题目要求

在这里插入图片描述
在这里插入图片描述

2、个人题解

2.1、解题思路

首先我们要弄清楚题目的含义:什么是连续子数组?

  • 子数组就是小数组里的元素,原数组里必须含义;加上连续,理解起来就是:该数组是原数组里的一串连续的元素或者单个元素。

搞清楚连续子数组后考虑该题的解法:

  1. 既然单个元素也属于连续子数组这个范畴,那么从第二个元素开始,我们对该元素和他与前一个元素的和比较,将二者中的较大值存到辅助数组dp中。
  2. 定义一个max作为最终的结果,并和数组dp中的元素不断对比,较大值将被赋值给max。
  3. 继续遍历,更新继续往dp数组中放入较大值,同时max也不断更新
  4. 遍历结束,max的值就是连续子数组的最大和

图示助理解:
在这里插入图片描述

2.2、代码实现

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.size()==1)
            return *array.begin();
        int dp[array.size()];
        int max=array[0];
        dp[0]=max;
        for(int i=1;i<array.size();i++){
            int temp=dp[i-1]+array[i];
            dp[i] = temp>array[i]? temp:array[i];
            if(dp[i]>max)
                max=dp[i];
        }
        return max;
    }
};

2.3、代码解析

  • 根据题目可知,数组长度是不小于1的,因此在长度为1的时候,直接返回即可
  • 根据数组长度设置辅助数组dp的长度,初始化dp首元素和max的值为数组首元素的值
  • 从第二个元素开始,将子数组和的最大值存入dp数组并更新max的值
  • 遍历结束后,返回max,程序结束,问题解决。

二、连续子数组的最大和(二)

1、题目要求

在这里插入图片描述
在这里插入图片描述

2、个人题解

2.1、解题思路

该题是在连续子数组的和最大的基础上,返回该连续子数组,这里仍然使用动态规划来解题:

 我们仍然要通过辅助数组dp来记录连续子数组的最大值,并根据最大值来更新连续子数组的区间,最后将最长区间作为数组下标,将区间范围的元素全部插入到要返回的数组中。


具体做法:

  1. 创建动态规划辅助数组,记录到下标i为止的最大连续子数组和,下标为0的时候,肯定等于原数组下标为0的元素。
  2. 准备左右区间双指针记录每次连续子数组的首尾,再准备两个双指针记录最大和且区间最长的连续子数组的首尾。
  3. 遍历数组,对于每个元素用上述状态转移公式记录其dp值,更新区间首尾(如果需要)。
  4. 出现一个最大值。且区间长度更大的时候,更新记录最长区间的双指针。
  5. 根据记录的最长子数组的位置取数组。

2.2、代码实现

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        // write code here
        if(array.size()==1)
            return array;
        vector<int>res;
        vector<int> dp(array.size(),0);
        dp[0]=array[0];
        int ans=dp[0];
        //滑动区间
        int left=0,right=0;
        //最终的区间范围
        int resl=0,resr=0;
        for(int i=1;i<array.size();i++){
            right++;
            //状态转移:连续子数组的最大值
            dp[i]=max(dp[i-1]+array[i], array[i]);
            //区间新起点
            if(dp[i-1]+array[i]<array[i])
                left=right;
            //更新最大值
            if(dp[i]>= ans)
            {
                ans=dp[i];
                resl=left;
                resr=right;
            }
        }
        //给res数组插入数据
        for(int i=resl;i<=resr;i++)
            res.push_back(array[i]);
        return res;
    }
};

2.3、代码解析

  • 根据题目可知,数组长度是不小于1的,因此在长度为1的时候,直接返回即可
  • 根据数组长度初始化辅助动态数组dp,最大值记为ans且默认为数组首元素的值
  • 声明遍历的区间以及最终的区间并初始化为0
  • 进入for循环,右区间right递增,将最大连续子数组的和存到dp数组中。
    • 如果是相加结果没有自身对应的元素值大,那么right将作为新区间的起点,即:left=right
    • 每次新存入dp数组的元素组和最大值ans比较:
      • 如果dp内的数据大,那么就更新最大值并让最终的区间等于遍历的区间
      • 如果dp内的数据小,不进行操作,最终区间范围不变
  • 随着遍历的进行,最终区间不断变化,遍历结束时,最终区间也就确定了下来
  • 最后根据区间将数组中的数据插入到ans数组中并返回

三、动态规划知识学习

动态规划算法的基本思想是:

  • 将待求解的问题分解成若干个相互联系的子问题,先求解子问题,然后从这些子问题的解得到原问题的解;
  • 对于重复出现的子问题,只在第一次遇到的时候对它进行求解,并把答案保存起来,让以后再次遇到时直接引用答案,不必重新求解。
  • 动态规划算法将问题的解决方案视为一系列决策的结果。