动态规划:路径和子数组问题(C++)

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

路径问题

1.不同路径(中等)

链接:不同路径

  • 题目描述
    动态规划:路径和子数组问题(C++),算法,动态规划,c++,算法,学习,笔记

  • 做题步骤

  1. 状态表示
    尝试定义状态表示为到达[m, n]位置的路径数
    动态规划:路径和子数组问题(C++),算法,动态规划,c++,算法,学习,笔记

  2. 状态转移方程
    通过上述分析,可知状态转移方程为:
    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

  3. 初始化
    动态规划:路径和子数组问题(C++),算法,动态规划,c++,算法,学习,笔记

  4. 填表顺序
    保证填当前状态时,所需状态已经计算过,从起点出发,填表顺序为从上往下,每一行从左往右

  5. 返回值
    根据状态表示,返回的应该是dp[m][n],即到达终点的路径数。

  • 代码实现
class Solution {
public:
    int uniquePaths(int m, int n) 
    {
        //dp[i][j]表示到达该位置的路径
        vector<vector<int>> dp(m+1, vector<int>(n+1,0));
        dp[0][1] = 1;

        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n;j++)
            {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        } 
	
        return dp[m][n];
        //时间复杂度:O(N)
        //空间复杂度:O(N^M)
    }
};

//滚动数组优化
// class Solution {
// public:
//     int uniquePaths(int m, int n) 
//     {
//         vector<int> dp(n + 1);
//         dp[1] = 1;

//         for(int i = 1; i <= m; i++)
//         {
//             for(int j = 1; j <= n;j++)
//             {
//                 dp[j] += dp[j-1];
//             }
//         } 
//         return dp[n];
//     }
// };

2.不同路径II(中等)

链接:不同路径II

  • 题目描述
    动态规划:路径和子数组问题(C++),算法,动态规划,c++,算法,学习,笔记

  • 做题步骤

  1. 状态表示
    这个题和第一题唯一不同就是加入了障碍物(1),我们只需要进行判断,如果该位置是障碍物就填0,否则依据转移方程填表

  2. 状态转移方程
    通过上述分析,可知状态转移方程为:
    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

  3. 初始化
    和第一题一样,多开一圈,dp[0][1]或dp[1][0]初始为1。

  4. 填表顺序
    和第一题一样,填表顺序为从上往下,每一行从左往右

  5. 返回值
    根据状态表示,返回的应该是dp[m][n],即到达终点的路径数。

  • 代码实现
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) 
    {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        //dp[i][j]:到达该位置的路径数
        vector<vector<int>> dp(m + 1,vector<int>(n + 1));
        dp[0][1] = 1; //dp[1][0] = 1;
        for(int i = 1; i < m + 1; i++)
        {
            for(int j = 1; j < n + 1; j++)
            {
                //多开了一圈,注意下标映射
                if(obstacleGrid[i - 1][j - 1] == 0)
                {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
                //vector默认初始0,障碍物对应位置无需处理
            }
        }
        return dp[m][n];
        //时间复杂度:O(N)
        //空间复杂度:O(N^2)
    }
};

3.下降路径最⼩和(中等)

链接:下降路径最⼩和

  • 题目描述
    动态规划:路径和子数组问题(C++),算法,动态规划,c++,算法,学习,笔记

  • 做题步骤

  1. 状态表示
    动态规划:路径和子数组问题(C++),算法,动态规划,c++,算法,学习,笔记

  2. 状态转移方程
    由前面的分析可知,状态转移方程为:
    dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]}) + matrix[i - 1][j - 1](本身的值)

  3. 初始化
    先全部初始化为极大值,然后第一行初始化为0

  4. 填表顺序
    从上往下,每一行从左往右。

  5. 返回值
    依据状态表示和题目要求,返回最后一行的最小值即可

  • 代码实现
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) 
    {
        //dp[i][j]表示到这个位置最小路径和
        int n = matrix.size();
        vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX));
        //初始化第一行
        for(int j = 0; j < n + 2; j++)
        {
            dp[0][j] = 0;
        }

        for(int i = 1; i < n + 1; i++)
        {
            for(int j = 1; j < n + 1; j++)
            {
                dp[i][j] = min({dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]})
                              + matrix[i - 1][j - 1]; 
            }
        }
        //再遍历一次找最小
        int ret = dp[n][0];
        for(auto e : dp[n])
        {
            ret = min(ret, e);           
        }
        return ret;
        //时间复杂度:O(N)
        //空间复杂度:O(N^2)
    }
};

4.地下城游戏(困难)

链接:地下城游戏

  • 题目描述

动态规划:路径和子数组问题(C++),算法,动态规划,c++,算法,学习,笔记

  • 做题步骤
  1. 状态表示

动态规划:路径和子数组问题(C++),算法,动态规划,c++,算法,学习,笔记

  1. 状态转移方程
    由前面的分析可知,状态转移方程为:
    dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j](自身出去的消耗)

  2. 初始化
    先将所有值初始化为极大值,dp[m][n - 1] = dp[m - 1][n] = 1。

  3. 填表顺序
    从下往上,每一行从右向左。

  4. 返回值
    由状态表示可知,返回值为dp[0][0](即[0,0]位置到终点需要的最小生命)

  • 代码实现
// 看点位的状态表示
//从左上到右下:点位表示到这里需要的最小健康点数,点位并不是只受到左边和上面的影响,也要受后面点位的影响(后面点位可能使自己死亡),这种状态表示肯定不能

//从右下到左上:点位表示从这里开始到终点所需要的最小健康点数。

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) 
    {
        //dp[i][j]表示以这个位置为起点到终点所需要的最小健康点数
        int m = dungeon.size();
        int n = dungeon[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        //初始化
        dp[m][n - 1] = dp[m - 1][n] = 1;
        for(int i = m - 1; i >= 0; i--)
        {
            for(int j = n - 1; j >=0; j--)
            {
                dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j];
                //如果dp[i][j]为负数,说明这个位置是奶
                //直接奶满了,从这里到终点所要的点数1就足够(小于1就死了)
                dp[i][j] = max(dp[i][j], 1);
            }
        }
        return dp[0][0];
        //时间复杂度:O(N)
        //空间复杂度:O(N^2)
    }
};

子数组问题

1.最大子数组和(中等)

链接:最大子数组和

  • 题目描述

动态规划:路径和子数组问题(C++),算法,动态规划,c++,算法,学习,笔记

  • 做题步骤
  1. 状态表示
    这个题目我们可以定义状态表示为以i位置为结尾的子数组的最大和
    因为子数组必须是连续的,所以i位置有两种选择:
    (1)接在以i - 1位置为结尾的子数组后面,即dp[i] = dp[i - 1] + 自身点数
    (2)不接在别人后面(可能dp[i - 1]是负值),就自己一个,即dp[i] = 自身点数
    从两种选择中选择最大的一种,即dp[i] = max(dp[i -1] + 自身点数, 自身点数)

  2. 状态转移方程
    由前面的分析可知,状态转移方程为:
    dp[i] = max(dp[i -1] + 自身点数, 自身点数)

  3. 初始化
    无需初始化。

  4. 填表顺序
    从左往右

  5. 返回值
    无法直接确定最大子数组的结尾位置,可以定义变量ret,一边dp一边更新最大值

  • 代码实现
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //在原数组上面dp就行
        //dp[i]:以i位置为结尾的最大子数组和
        int ret = nums[0];
        for(int i = 1; i < nums.size(); i++)
        {
            nums[i] = max(nums[i - 1] + nums[i], nums[i]);
            //遍历的过程顺便找最大
            ret = max(ret, nums[i]);      
        }                
        return ret;
        //时间复杂度:O(N)
        //空间复杂度:O(1)
    }
};

2.环形子数组的最大和(中等)

链接:环形子数组的最大和

  • 题目描述
    动态规划:路径和子数组问题(C++),算法,动态规划,c++,算法,学习,笔记

  • 做题步骤

  1. 状态表示
    这个题目和前一题类似,我们依然可以定义状态表示为以i位置为结尾的最大子数组和

    对于环形问题,最常见的做法就是分情况讨论,分解问题:
    (1)最大子数组不成环,比如[-1,2,3,-1],这个情况做法和前一道题一样

    (2)最大子数组成环,比如[2,1,-3,-2,1],最大子数组成环情况,数组中剩余的连续部分一定是最小子数组
    子数组是连续的,环形可以理解为左右扩张,所有有利于自己的连续部分一定会被吞并,剩下的一定是最小子数组和。
    但数组的总和是不变的,我们只需要用总和减去最小子数组和即可得到成环情况的最大和

  2. 状态转移方程
    不成环最大子数组和用f表来记录,最小子数组和用g表来记录
    状态转移方程为:
    f[i] = max(nums[i], f[i - 1] + nums[i])
    g[i] = min(nums[i], g[i - 1] + nums[i])

  3. 初始化
    为避免填表越界,处理第一个位置,f[0] = g[0] = nums[0]

  4. 填表顺序
    都是从左往右

  5. 返回值
    无法直接确定最大(小)子数组的结尾,所以一边dp一边记录最大(小)值
    (1)f表最大值->fmax
    (2)g表最小值->gmin
    (3)总和->sum
    还有一种特殊情况就是环形数组长度为0(数组中全是负数),这个时候最大值为fmax而不是0,所以返回值为sum == gmin ? fmax : max(fmax, sum - gmin)

  • 代码实现
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();
        //一种情况是不需要环形,区间就在数组中
         //第二种情况是需要环形,数组总大小恒定
        //非目标区间是连续并且在数组中的,所以最大 = 总 - 非目标区间
        //比如 5 -3 5,第一种得到5,第二种为 7(总) - (-3) = 10
        int sum = nums[0];
        //f[i]:以i位置为结尾的不成环最大子数组和
        vector<int> f(n);
        //g[i]:以i位置为结尾的最小子数组和
        auto g = f;
        f[0] = g[0] = nums[0];
        int fmax = nums[0];
        int gmin = nums[0];
        for(int i = 1; i < n; i++)
        {
            f[i] = max(nums[i], f[i - 1] + nums[i]);
            g[i] = min(nums[i], g[i - 1] + nums[i]);
            fmax = max(fmax, f[i]);
            gmin = min(gmin, g[i]);
            sum += nums[i];
        }
        //sum和gmin相同说明里面全是负数,这个时候fmax才是最大,不能为0
        return sum == gmin ? fmax : max(fmax, sum - gmin);
        //时间复杂度:O(N)
        //空间复杂度:O(N)
    }
};

3.乘积最大子数组(中等)

链接:乘积最大子数组

  • 题目描述
    动态规划:路径和子数组问题(C++),算法,动态规划,c++,算法,学习,笔记

  • 做题步骤

这个题目子数组长度最小可以为1,其实所有子数组默认乘了一个1

  1. 状态表示
    依据前面最大子数组和的经验,我们可以定义状态为以i位置为结尾的最大乘积

    但只有这一个状态表示是不够的,负数的加入对乘积影响是巨大的,比如[1,2,3,-1,-2,1],前面按最大和的做法来还没问题,但遇到多个负数就会出问题,这里[1,2,3,-1,-2]可以得到最大乘积12,如果按照最大和的做法只能得到6。

    出现上面情况的原因在于负数的出现使得原来的最大乘积变成了最小乘积,但如果保存最小乘积,当遇到负数时最小乘积就可以变成最大乘积

    综上所述,我们需要同时记录最大和最小乘积,其中最大用f表记录,最小用g表记录。
    (1)x = nums[i](当前位置的值)
    (2)y = f[i - 1](前一个位置的最大乘积)
    (3)z = g[i - 1](前一个位置的最小乘积)

  2. 状态转移方程
    一共就三种情况:
    (1)x:不接在别人后面,子数组长度为1。
    (2)x * y:接在前一个位置最大乘积子数组后面,有可能得到最大(小)乘积。
    (3)y * z:接在前一个位置最小乘积子数组后面,有可能得到最大(小)乘积。

    由此可知状态转移方程为:
    f[i] = max( {x, x * y, x * z} )
    g[i] = min( {x, x * y, x * z} )

  3. 初始化
    当前位置的f、g更新需要前一个位置,第一个位置的最大(小)乘积就是值本身,为了避免第一个位置越界,可以在前面多开一个空间并初始化为1,即f[0] = g[0] = 1,这样不会影响第一个位置。

  4. 填表顺序
    从左往右。

  5. 返回值
    无法直接确定最大子数组的结尾位置,一边dp一边更新最大值

  • 代码实现
class Solution {
public:
    int maxProduct(vector<int>& nums) 
    {
        int n  = nums.size();
        //dp[i]:以i为结尾的最大乘积
        //f[i]表示最大乘积,g[i]表示最小乘积
        vector<int> f(n + 1);
        auto g = f;
        f[0] = g[0] = 1;
        //ret变量记录最大乘积
        int ret = INT_MIN;
        for(int i = 1; i <= n; i++)
        {
            int x = nums[i - 1];//现在
            int y = f[i - 1]; //上个位置的最大乘积
            int z = g[i - 1]; //上个位置的最小乘积
            //如果遇到负数的情况,原本最大乘积可能会变成最小,原本最小可能会变成最大
            f[i] = max({x, x * y, x * z});
            g[i] = min({x, x * y, x * z});
            ret = max(ret, f[i]);
        }
        return ret;
        //时间复杂度:O(N)
        //空间复杂度:O(N)
    }
};

4.乘积为正数的最长子数组(中等)

链接:乘积为正数的最长子数组

  • 题目描述
    动态规划:路径和子数组问题(C++),算法,动态规划,c++,算法,学习,笔记

  • 做题步骤

  1. 状态表示
    这个题目和上一道类似,要考虑负数的加入,因此只有一个状态表示是不够的。
    (1)f表:以i位置为结尾,乘积为正数的最长子数组长度。
    (2)g表:以i位置为结尾,乘积为负数的最长子数组长度。

  2. 状态转移方程
    设当前位置的值为x
    (1)x为负数时,接在前一个位置的后面,原本乘积正数的子数组会变成负数,乘积负数的子数组会变成正数。
    即f[i] = g[i - 1] + 1 和 g[i] = f[i - 1] + 1,但前一个位置结尾的子数组乘积可能无法出现负数(前面都是正数),即g[i - 1] == 0,这个时候f[i]应该也为0。
    故状态转移方程为:
    f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1
    g[i] = f[i - 1] + 1


    (2)当x为正数时,接在前一个位置的后面,原本乘积正数的子数组还是正数,乘积负数的子数组还是负数。
    (也要考虑前一个位置乘积负数不存在的情况
    故状态转移方程为:
    f[i] = f[i - 1] + 1
    g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1

  3. 初始化
    当前位置的f、g更新需要前一个位置,第一个位置为负数,g[i]为1,f[i]为0,值为正数则相反。为了避免第一个位置越界,可以在前面多开一个空间并初始化为0,即f[0] = g[0] = 0,这样不会影响第一个位置。

  4. 填表顺序
    保证填当前状态时,所需状态已经计算过,填表顺序很明显是从左往右

  5. 返回值
    无法直接确定乘积为正数的最长子数组结尾位置,定义变量ret,一边dp一边更新最大值

  • 代码实现
class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        //dp[i] 表示这个位置乘积为负数/正数时的最大长度
        int n = nums.size();
        vector<int> f(n + 1); // 正数
        auto g = f;//负数
        int ret = -1;
        for(int i = 1; i < n + 1; i++)
        {
            //这个数是正数
            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;           
            }
            //这个数为0,两个状态都不存在,不用处理(本来就是0)
            ret = max(ret, f[i]);
        }
        return ret;
        //时间复杂度:O(N)
        //空间复杂度:O(N)
    }
};

5.等差数列划分(中等)

链接:等差数列划分

  • 题目描述

动态规划:路径和子数组问题(C++),算法,动态规划,c++,算法,学习,笔记

  • 做题步骤
  1. 状态表示
    依据前面的经验,我们可以定义状态表示为以i位置为结尾的等差数组个数

  2. 状态转移方程
    以[1,2,3,4]为例子进行分析:
    (1)像1、2这样的位置为结尾数组长度不足3,是一定不能构成等差数组的,即dp[i] = 0。
    (2)像4这样的位置,先看能不能和前面两个元素构成等差数组(满足nums[i] + nums[i - 2] == 2* nums[i - 1]),如果可以的话那4也一定可以接在以3为结尾的等差数组后面,即dp[i] = dp[i - 1] + 1。

    综上所述,状态转移方程为:
    可以和前两个数构成等差数组:dp[i] = dp[i - 1] + 1
    不能和前两个数构造等差数组:dp[i] = 0

  3. 初始化
    无需初始化。

  4. 填表顺序
    保证填当前状态时,所需状态已经计算过,填表顺序很明显是从左往右

  5. 返回值
    题目要求返回所有等差子数组,定义变量sum,一边dp一边累加

  • 代码实现
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        // 1 2 3 4 5
        //3位置1种   4位置除了拼在3位置可能的后面,还可以抢2 3 来组成
        //4位置2种   5位置除了拼在4位置可能的后面,还可以抢3 4 来组成
        //………………对更长的序列也是如此
        int n = nums.size();
        //dp[i]:以i位置为结尾的等差数组个数
        vector<int> dp(n);
        int sum = 0;
        for(int i = 2; i < n; i++)
        {
            //等差数列的性质:num[i] + nums[i - 2] == 2 * num[i - 1]
            if(nums[i] + nums[i - 2] == 2* nums[i - 1])
            {
                dp[i] = dp[i - 1] + 1;
            }
            //不满足等差数组为0,vector默认给0,不用处理
            sum += dp[i];
        }
        return sum;
        //时间复杂度:O(N)
        //空间复杂度:O(N)
    }
};

6.最长湍流子数组(中等)

链接:最长湍流子数组

  • 题目描述
    动态规划:路径和子数组问题(C++),算法,动态规划,c++,算法,学习,笔记

  • 做题步骤

  1. 状态表示
    依据前面的经验,我们定义状态表示为以i位置为结尾的最长湍流子数组长度

    但只知道i-1位置的最大长度是无法推导出i位置的最大长度的,因为不知道前一个最长湍流子数组结束是处于上升状态(最后的比较符号为’<‘)还是下降状态(最后的比较符号为’>')

    因此可以对状态进行细分:
    (1)f[i]表示以i位置为结尾并处于上升状态(最后的比较符号为’<')的最长湍流子数组长度
    (2)g[i]表示以i位置为结尾并处于下降状态(最后的比较符号为’>')的最长湍流子数组长度

  2. 状态转移方程
    因为湍流子数组比较符号必须在每个相邻元素之间翻转,所以状态转移方程与当前的比较符号相关。
    (1)arr[i-1] < arr[i],现在处于上升状态,需要前置状态处于下降状态的最长湍流子数组长度,即f[i] = g[i - 1] + 1
    (2)arr[i-1] > arr[i],现在处于下降状态,需要前置状态处于上升状态的最长湍流子数组长度,即g[i] = f[i - 1] + 1
    (3)arr[i-1] = arr[i],不能和前面组合,只能自己重新开始,即f[i] = g[i] = 1

  3. 初始化
    推导当前状态需要前一个状态,像第一个位置不能跟在别人后面,两个状态的长度都为1,f[0] = g[0] = 1。因为arr[i-1] = arr[i]时f[i] = g[i] = 1,所以干脆一开始全都初始化为1,就不用单独处理arr[i-1] = arr[i]的情况。

  4. 填表顺序
    保证填当前状态时,所需状态已经计算过,填表顺序很明显是从左往右

  5. 返回值
    无法直接确定最长湍流数组的结尾位置以及结尾是处于上升还是下降状态,所以定义变量ret,一边dp一边更新最大值

  • 代码实现
class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size();
        //dp[i]表示以i位置为结尾并且处于上升(下降)状态的最长湍流子数组的长度 
        vector<int> f(n, 1); //f表示处于上升(<)状态
        //初始化为1,可以把'=='的情况直接处理了
        auto g = f; //g表示处于下降(>)状态
        int ret = 1;
        for(int i = 1; i < n; i++)
        {
            if(arr[i-1] < arr[i])
                f[i] = g[i - 1] + 1;
            else if(arr[i - 1] > arr[i])
                g[i] = f[i - 1] + 1;
            ret = max( {ret, f[i], g[i]} );
        }
        return ret;
        //时间复杂度:O(N)
        //空间复杂度:O(N)
    }
};

7.单词拆分(中等)

链接:单词拆分

  • 题目描述

动态规划:路径和子数组问题(C++),算法,动态规划,c++,算法,学习,笔记

  • 做题步骤
  1. 状态表示
    依据前面的经验,我们可以定义状态表示为以i位置为结尾的字符串能否由字典中的单词拼出

  2. 状态转移方程
    以s = “leetcode”, wordDict = [“leet”, “code”]为例进行分析:
    (1)先看字符’t’位置(下标3位置),以这个位置为结尾的字符串如果能由字典中的单词拼出,一共有下面几种可能:
    ①"lee"可以由字典中的单词拼出(即dp[2] = true),"t"也可以由字典中的单词拼出。
    ②"le"可以由字典中的单词拼出(即dp[1] = true),"et"也可以由字典中的单词拼出。
    ③"l"可以由单词中的单词拼出(即dp[0] = true),"eet"也可以由字典中的单词拼出。
    ④再往前就没有了,"leet"可以由字典中的单词拼出。

    其它位置的分析也和上述一致,将当前字符串分成[0, j - 1]区间和[j, i]区间,从 0 ~ i 枚举 j ,只要 dp[j - 1] = true并且后面部分的子串 s.substr(j, i - j + 1) 能够在字典中找到,那么 dp[i] = true 。

  3. 初始化
    处理④这样的情况,可以多加一个虚拟节点并初始化true(dp[0] = true),可以理解为空串能在字典中找到。同时为了方便处理下标的映射关系,我们可以在字符串s前面加一个占位符(s = ’ ’ + s),这样就不用考虑下标的映射了。

  4. 填表顺序
    保证填当前状态时,所需状态已经计算过,填表顺序很明显是从左往右

  5. 返回值
    根据状态表示,假设字符串长度为n,返回的应该是dp[n]

  6. 优化
    为了方便查询字符串是否在字典中,可以把字典的单词存储到哈希表中

  • 代码实现
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; // 使原始字符串的下标统⼀ 
        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];
        //时间复杂度:O(N^2)
        //空间复杂度:O(N)
    }
};

8.环绕字符串中唯⼀的子字符串(中等)

链接:环绕字符串中唯⼀的子字符串

  • 题目描述

动态规划:路径和子数组问题(C++),算法,动态规划,c++,算法,学习,笔记

  • 做题步骤
  1. 状态表示
    依据前面的经验,我们定义状态表示为以i位置为结尾并且在base中出现的子字符串个数

  2. 状态转移方程
    这个题目中的base数组是按照abcd……zabcd这样的顺序来的,要注意base成环。
    以i位置为结尾并在base中出现的子字符串有下面三种可能:
    (1)不拼在别人后面,就单独自己一个,该字符串一定会在base中出现。
    (2)拼在别人后面,并且满足s[i] = s[i - 1] + 1(即满足abcd递增)
    (3)拼在别人后面,并且满足s[i] == ‘a’ && s[i - 1] == ‘z’(刚好成环)

    综上所述,状态转移方程为:
    ①满足(2)(3)中任意一个,dp[i] = dp[i - 1] + 1(这个1是自己,dp[i - 1]是拼在别人后面)
    ②不满足(2)(3),dp[i] = 1

  3. 初始化
    每个位置最少也有自己单独一个的情况,所以全都初始化为1

  4. 填表顺序
    保证填当前状态时,所需状态已经计算过,填表顺序很明显是从左往右

  5. 返回值
    这个题目最需要注意的就是对dp表数据的处理,因为dp表中可能有大量重复的数据,比如"abcdcd"中’d’字符出现了两次,"cd"和"d"这两个字符串在dp表中是多次记录了的,我们需要对dp表数据进行去重。

    每个字符都对应了固定的ASCLL码,因此可以可以创建⼀个大小为 26 的数组,遍历dp表,对于出现多次的字符,只需保留以该字符为结尾的最大dp值

    去重完成后再进行累加就可以得到结果。文章来源地址https://www.toymoban.com/news/detail-695097.html

  • 代码实现
class Solution {
public:
    int findSubstringInWraproundString(string s) {
        //base是abcd……连续的
        //s[i]表示现在位置
        //所以字串要存在要么s[i] == s[i - 1] + 1
        //要么(s[i - 1] == 'z' && a[i]=='a') 
        int n = s.size();
        //dp[i]:以i位置为结尾并且在base中出现的子字符串数
        vector<int> dp(n, 1);
        for(int i = 1; i < n; i++)
        {
            if(s[i] == s[i-1] + 1 || (s[i-1] == 'z' && s[i] == 'a'))
            {
                dp[i] = dp[i - 1] + 1; // 这个1是自己
            }
        }
        int hash[26] = {0};
        //遍历一次,统计对应字符最大的出现次数
        //"abcdd"这样的后面那个d的1是无效的,要去掉
        for(int i = 0; i < n; i++)
        {
            int index = s[i] - 'a';
            hash[index] = max(hash[index], dp[i]);
        }
        //最后累加
        int sum = 0;
        for(auto e : hash)
        {
            sum += e;
        }
        return sum;
        //时间复杂度:O(N)
        //空间复杂度:O(N)
    }
};

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

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

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

相关文章

  • 【算法优选】 动态规划之路径问题——贰

    动态规划相关题目都可以参考以下五个步骤进行解答: 状态表⽰ 状态转移⽅程 初始化 填表顺序 返回值 后面题的解答思路也将按照这五个步骤进行讲解。 给你一个 n x n 的 方形 整数数组 matrix ,请你找出并返回通过 matrix 的下降路径 的 最小和 。 下降路径 可以从第一行中的

    2024年02月05日
    浏览(49)
  • 【算法】动态规划中的路径问题

    君兮_的个人主页 即使走的再远,也勿忘启程时的初心 C/C++ 游戏开发 Hello,米娜桑们,这里是君兮_,如果给算法的难度和复杂度排一个排名,那么动态规划算法一定名列前茅。今天,我们通过由简单到困难的两道题目带大家学会动态规划中的路径问题 好了废话不多说,开始我

    2024年02月05日
    浏览(38)
  • c++ 子数组动态规划问题

    1.最大子数组和   力扣 给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组 是数组中的一个连续部分。 示例 1: 示例 2: 示例 3: 2.环形子数组最大和 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 给

    2024年02月12日
    浏览(39)
  • 基础算法之——【动态规划之路径问题】1

    今天更新动态规划路径问题1,后续会继续更新其他有关动态规划的问题!动态规划的路径问题,顾名思义,就是和路径相关的问题。当然,我们是从最简单的找路径开始! 动态规划的使用方法: 1.确定状态并定义状态数组:(i,j)代表什么意思?dp[i][j]又是什么意思? 2.确

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

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

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

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

    2024年02月07日
    浏览(55)
  • 动态规划:两个数组的dp问题(C++)

    动态规划往期文章: 动态规划入门:斐波那契数列模型以及多状态 动态规划:路径和子数组问题 动态规划:子序列问题 动态规划:回文串问题 1.最长公共子序列(中等) 链接 :最长公共子序列 题目描述 做题步骤 状态表示 对于两个数组的dp,采用一维dp是没有办法清晰的表

    2024年02月08日
    浏览(51)
  • 【动态规划】【滑动窗口】【C++算法】 629K 个逆序对数组

    视频算法专题 动态规划汇总 C++算法:滑动窗口总结 逆序对的定义如下:对于数组 nums 的第 i 个和第 j 个元素,如果满足 0 = i j nums.length 且 nums[i] nums[j],则其为一个逆序对;否则不是。 给你两个整数 n 和 k,找出所有包含从 1 到 n 的数字,且恰好拥有 k 个 逆序对 的不同的数

    2024年01月17日
    浏览(44)
  • 算法沉淀——动态规划篇(子数组系列问题(下))

    几乎所有的动态规划问题大致可分为以下5个步骤,后续所有问题分析都将基于此 1.、状态表示:通常状态表示分为以下两种,其中更是第一种为主。 以i为结尾 ,dp[i] 表示什么,通常为代求问题(具体依题目而定) 以i为开始 ,dp[i]表示什么,通常为代求问题(具体依题目而

    2024年04月14日
    浏览(52)
  • C++算法初级11——01背包问题(动态规划2)

    辰辰采药 辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时

    2024年02月02日
    浏览(50)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包