动态规划：路径和子数组问题（C++）

动态规划：路径和子数组问题

• • 路径问题
  • • 1.不同路径（中等）
    • 2.不同路径II（中等）
    • 3.下降路径最⼩和（中等）
    • 4.地下城游戏（困难）
    • 子数组问题
    • • 1.最大子数组和（中等）
      • 2.环形子数组的最大和（中等）
      • 3.乘积最大子数组（中等）
      • 4.乘积为正数的最长子数组（中等）
      • 5.等差数列划分（中等）
      • 6.最长湍流子数组（中等）
      • 7.单词拆分（中等）
      • 8.���绕字符串中唯⼀的子字符串（中等）

        路径问题

        1.不同路径（中等）

        链接：不同路径

        • 题目描述

        • 做题步骤

          1. 状态表示

             尝试定义状态表示为到达[m, n]位置的路径数。

          2. 状态转移方程

             通过上述分析，可知状态转移方程为：
             dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

          3. 初始化

          4. 填表顺序

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

          5. 返回值

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

          • 代码实现

            class Solution {public:    int uniquePaths(int m, int n)     {        //dp[i][j]表示到达该位置的路径        vector dp(m+1, vector(n+1,0));        dp[0][1] = 1;        for(int i = 1; i             for(int j = 1; 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//             for(int j = 1; j //                 dp[j] += dp[j-1];//             }//         } //         return dp[n];//     }// };public:    int uniquePathsWithObstacles(vector        int m = obstacleGrid.size();        int n = obstacleGrid[0].size();        //dp[i][j]：到达该位置的路径数        vector            for(int j = 1; j gmin
            (3)总和->sum
            还有一种特殊情况就是环形数组长度为0(数组中全是负数)，这个时候最大值为fmax而不是0，所以返回值为sum == gmin ? fmax : max(fmax, sum - gmin)。
             

          • 代码实现

            class Solution {public:    int maxSubarraySumCircular(vector& nums) {        int n = nums.size();        //一种情况是不需要环形，区间就在数组中         //第二种情况是需要环形，数组总大小恒定        //非目标区间是连续并且在数组中的，所以最大 = 总 - 非目标区间        //比如 5 -3 5，第一种得到5，第二种为 7(总) - (-3) = 10        int sum = nums[0];        //f[i]：以i位置为结尾的不成环最大子数组和        vector 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  
            3.乘积最大子数组（中等）
             
            链接：乘积最大子数组
             

            • 题目描述

            • 做题步骤

              这个题目子数组长度最小可以为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& nums)     {        int n  = nums.size();        //dp[i]：以i为结尾的最大乘积        //f[i]表示最大乘积，g[i]表示最小乘积        vector f(n + 1);        auto g = f;        f[0] = g[0] = 1;        //ret变量记录最大乘积        int ret = INT_MIN;        for(int i = 1; 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)    }};public:    int getMaxLen(vector        //dp[i] 表示这个位置乘积为负数/正数时的最大长度        int n = nums.size();        vector            //这个数是正数            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]  
                5.等差数列划分（中等）
                 
                链接：等差数列划分
                 

                • 题目描述
                  • 做题步骤

                    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& 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 dp(n);        int sum = 0;        for(int i = 2; i  
                      6.最长湍流子数组（中等）
                       
                      链接：最长湍流子数组
                       

                      • 题目描述

                      • 做题步骤

                        1. 状态表示

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

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

                           因此可以对状态进行细分：

                           （1）f[i]表示以i位置为结尾并处于上升状态(最后的比较符号为’ arr[i]，现在处于下降状态，需要前置状态处于上升状态的最长湍流子数组长度，即g[i] = f[i - 1] + 1。

                           （3）arr[i-1] = arr[i]，不能和前面组合，只能自己重新开始，即f[i] = g[i] = 1。

                        2. 初始化

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

                        3. 填表顺序

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

                        4. 返回值

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

                        • 代码实现

                          class Solution {public:    int maxTurbulenceSize(vector& arr) {        int n = arr.size();        //dp[i]表示以i位置为结尾并且处于上升(下降)状态的最长湍流子数组的长度         vector f(n, 1); //f表示处于上升()状态        int ret = 1;        for(int i = 1; i  arr[i])                g[i] = f[i - 1] + 1;            ret = max( {ret, f[i], g[i]} );        }        return ret;        //时间复杂度：O(N)        //空间复杂度：O(N)    }};

                          7.单词拆分（中等）

                          链接：单词拆分

                          • 题目描述
                            • 做题步骤

                              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& wordDict)     {        // 将字典⾥⾯的单词存在哈希表⾥⾯        unordered_set hash;        for(auto& s : wordDict) hash.insert(s);        int n = s.size();        vector dp(n + 1);        dp[0] = true; // 保证后续填表是正确的        s = ' ' + s; // 使原始字符串的下标统⼀         for(int i = 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; //已经确定为真就可以跳出这一层循环了                }            }        }        return dp[n];        //时间复杂度：O(N^2)        //空间复杂度：O(N)    }};

                                8.环绕字符串中唯⼀的子字符串（中等）

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

                                • 题目描述
                                  • 做题步骤

                                    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值。
                                       

                                       去重完成后再进行累加就可以得到结果。

                                    • 代码实现

                                      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 dp(n, 1);        for(int i = 1; i