开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 动态规划之线性DP题集 -> 正文阅读

[数据结构与算法]动态规划之线性DP题集

动态规划之线性DP

（一）LIS问题

最大子序和

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8GqFJPdk-1631977136451)(D:\github\gitee\leet-book-solutoin\动态规划\动规专题\动态规划之线性DP.assets\1631543057632.png)]$

（动规）

1.状态定义

同样还是只能在一个序列中求出子序列的和，所以只有一个限制，所以可以使用一维数组来保存即可。

dp[i]表示以第i数结尾的连续子数组的和的最大值为dp[i]。

2.递推公式

因为是求出连续的子数组的和，所以考虑状态转移的时候只需要考虑前面一个状态即可，即dp[i - 1] + nums[i]和nums[i]比较，取一个最大值即可。

3.初始化

每一个数字都是一个连续的子数组，所以以i结尾的连续子数组的和至少为nums[i]，这个可以在循环的时候赋值在dp[i]上即可。

4.遍历顺序

由递推公式可知，一个状态只由前一个状态决定，所以从前往后遍历即可。

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

（贪心）

我们可以贪心的发现，如果前面一个连续子数组的和sum > 0，那么对于第i个数结尾的连续子数组来说，可以使得这个子数组的和增大，所以sum += nums[i]，否则，如果前面的子数组的和<0，那么以i结尾的数字如果自己为一个子数组的话，可以获得更大的子数组和，这时选择nums[i]。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = INT_MIN, sum = 0;
        for (int i = 0; i < nums.size(); i ++) {
            if (sum > 0) {
                sum += nums[i];
            } else {
                sum = nums[i];
            }
            ans = max(ans, sum);
        }
        return ans;
    }
};

最长连续递增序列

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-m9qM0WdT-1631977136452)(D:\github\gitee\leet-book-solutoin\动态规划\动规专题\动态规划之线性DP.assets\1631545541300.png)]$

（动规）

本题就是最长上升子序列的一个退化版本。即当前的状态只有前面一个状态转移过来，所以只有当nums[i] > nums[i - 1]的时候，以i结尾的连续子数组的长度才+1。其余的情况，只有nums[i]这一个数字充当连续的子数组，长度为1。第一题和第二题如果理解的话，本题应该就没有太大的问题了，这里就不详细讲了。

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

（双指针）

也可以利用经典的双指针算法，将连续的子数组抠出来，然后计算出子数组的长度即可。最后比较所有的连续子数组的长度。

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < n; i ++) {
            int j = i + 1;
            while (j < n && nums[j] > nums[j - 1]) j ++;
            ans = max(ans, j - i);
            i = j - 1;
        }
        return ans;
    }
};

俄罗斯套娃信封问题

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cehNIWa0-1631977136454)(D:\github\gitee\leet-book-solutoin\动态规划\动规专题\动态规划之线性DP.assets\1631606400998.png)]$

只有一个信封的h和w都比另一个信封大的时候，才可以将信封套住，其实我们就是要寻找可以套住当前信封的信封，所以就要找一系列连续的大信封，这样就可以才可以一环套一环。

**每一次合法的嵌套都是大的套小的信封，所以就相当于找一个最长上升子序列，其长度就是信封可以嵌套的信封数量。**所以这道题目本质上是一个最长上升子序列问题。

（二维LIS问题动规）

如果将二维的数组看做一个整体，然后求出最长上升的子序列，那么就可以直接利用envelopes[i]0和envelopes[i][1]进行比较即可。

但是首先需要将数组进行一个排序。因为只有当信封的大小是升序排序的时候，选择出的最长上升子序列才是有意义的。

至于DP分析的过程，除了递推公式判断的时候需要判断envelopes[i]0和envelopes[i][1]这两个条件之外，其余的分析的过程都是一样的。

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();
        vector<int> dp(n, 0);
        sort(envelopes.begin(), envelopes.end());
        int ans = 1;
        for (int i = 0; i < n; i ++) {
            dp[i] = 1;
            for (int j = 0; j < i; j ++) {
                if (envelopes[i][0] > envelopes[j][0] && 
                    envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

（一维LIS问题）

如果觉得二维分析的时候有一些麻烦，其实也是可以常见的思维方式，即减少变量。

我们可以将h和w其中的一个先固定下来，比如说是w，可以对w进行升序排序；然后就可以直接对数组中的第二维进行最长上升子序列的dp分析过程即可。

但是注意有一些特殊情况的时候，就不能满足。当多个数组中的第一维是相等的时候，如(1, 2), (1, 3), (1, 4)这时候其实因为信封的h并没有严格的大于。所以是没有信封可以嵌套的，但是如果只是用数组中的第二维进行排序的话，最长上升子序列的长度却是3个，这时其实就出现了冲突。

为了避免这种情况的出现，当数组中第一维数字相同的时候，我们就不应该将有相同的第一维的数字算在最上升子序列中**。解决的方式是：可以在排序的是对第一维升序排序，但是如果第一维相同的情况下，进行降序排序。**这样在计算第二维的时候，就可以避免冲突了。

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();
        vector<int> dp(n, 0);
        // 对第一维升序，在相同的情况下第二维降序
        sort(envelopes.begin(), envelopes.end(), [](vector<int>& a, vector<int>&b){
            if (a[0] != b[0]) return a[0] < b[0];
            return a[1] > b[1];
        });
        int ans = 0;
        for (int i = 0; i < n; i ++) {
            dp[i] = 1;
            for (int j = 0; j < i; j ++) {
                if (envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

（一维LIS问题+二分贪心优化）

其实固定了第一维之后在进行一维的LIS问题，时间复杂度并没有降低。但是二维LIS变成一维的LIS，最大的好处是：一维的上升子序列可以使用二分+贪心的优化（前面的题目中说过）这就可以使得时间复杂度变成O(log_N)了，但是二维的上升子序列在比较大小的时候不是很方便，所以就不采取二分的优化了。

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();
        sort(envelopes.begin(), envelopes.end(), [](vector<int>& a,vector<int>& b){
            if (a[0] != b[0]) return a[0] < b[0];
            return a[1] > b[1];
        });
        int ans = 0;
        vector<int> dp;
        for (int i = 0; i < n; i ++) {
            auto it = lower_bound(dp.begin(), dp.end(), envelopes[i][1]);
            ans = fmax(ans, it - dp.begin() + 1);
            if (it == dp.end()) dp.push_back(envelopes[i][1]);
            else *it = envelopes[i][1];
        }
        return ans;
    }
};

堆箱子

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QhFPRYbs-1631977136455)(D:\github\gitee\leet-book-solutoin\动态规划\动规专题\动态规划之线性DP.assets\1631609633988.png)]$

（三维LIS问题动规）

刚刚上面的题目是二维的LIS问题，本题就是三维的LIS问题。

其实还有比较两个数组的大小问题，只不过是又多了一维而已，我们只需要在if判断的时候，多加一个条件即可。

但是有两个注意点：

1.本题不可以降维使用二分优化，因为三维空间就算使用排序固定一维，但是二维还是不可以二分的优化。

2.本题和普通的LIS问题不同的是，本题不是直接求出最长上升子序列的长度。而是在满足最长上升子序列的条件下，计算累加的高度。所以递推公式不再是dp[i] = max(dp[i], dp[j] + 1)，而是如果满足上升的性质的时候，需要累加箱子的高度。

即dp[i]表示为以第i个箱子为底的箱子，上面累加的最高的高度为dp[i]。所以递推公式是在转移i的状态高度上累加第j个箱子上应该放上box[i][2]。即递推公式为dp[i] = max(dp[i], dp[j] + box[i][2])

class Solution {
public:
    int pileBox(vector<vector<int>>& box) {
        int n = box.size();
        int ans = 0;
        sort(box.begin(), box.end(), greater<vector<int>>());
        vector<int> dp(n);
        for (int i = 0; i < n; i ++) {
            dp[i] = box[i][2];
            for (int j = 0; j < i; j ++) {
                if (box[i][0] < box[j][0] && box[i][1] < box[j][1] 
                    					  && box[i][2] < box[j][2]){
                    dp[i] = max(dp[i], dp[j] + box[i][2]);
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;      
    }
};

无重叠区间

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XnvRKyfY-1631977136456)(D:\github\gitee\leet-book-solutoin\动态规划\动规专题\动态规划之线性DP.assets\1631628385619.png)]$

（动规）

本题直接求出取出的最小区间数其实不太好算，但是如果算出无重复的区间数，就使得区间之间有了单调性。

但题目转化为了求出无重复区间的数量的时候，就可以利用类似最长上升子序列的动规方法剞劂本题。

1.状态定义

dp[i]表示以i结尾的区间，前面的区间中最多有dp[i]个无重复的区间数。

2.递推公式

现在处于第i个区间，那么此时如果想要让第i个区间在无重复的区间中，就必须枚举前i个区间中是否存在intervals[j][1]小于intervals[i][0]，这样的话就可以使得第i个区间放在第j个区间中。所以递推公式为dp[i] = max(dp[i], dp[j] + 1)。

这个递推公式其实和LIS问题的递推公式是一样的，其实两个题目的思想都是一样的。可以说本题其实就是求出最长不重复区间的序列数量。两道题目都是在序列中找，当满足某一个性质的时候（可能是必须满足递增的序列或者是满足不重复区间的序列）状态可以转移。

3.初始化

每一个区间都至少是一个不重复的区间，所以可以将dp数组都初始化为1

注意：由于区间是二维的，所以不能使用二分的优化，所以O(N²)的效率是很低的。

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        sort(intervals.begin(), intervals.end());
        int n = intervals.size();
        vector<int> dp(n, 0);
        int max_elem = 0;  // 无重复区间的最大数量
        for (int i = 0; i < n; i ++) {
            dp[i] = 1;
            for (int j = 0; j < i; j ++) {
                if (intervals[i][0] >= intervals[j][1]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            max_elem = max(max_elem, dp[i]);
        }
        return n - max_elem;
    }
};

本题也可以利用贪心的思想，我们可以贪心地想：当排完序之后，要得到最小的重复区间数，也就是得到最多的无重复区间数。那么每一次两个区间如果重叠的话，我们取区间右边界小的一个区间作为下一次判断的右边界。

因为如果右边界大的话，下一次要满足无重复区间的左边界就会变大，这样满足条件的区间就会变少。所以我们贪心地选取右边界小的区间。

实现这样贪心的方式有两种：第一种就是求出移除的区间数，第二种就是求出无重复区间的最大数量，然后最后用intervals.size()减一下即可。

（贪心1）

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        sort(intervals.begin(), intervals.end());
        int ans = 0;
        int r = intervals[0][1];
        int n = intervals.size();
        for (int i = 1; i < n; i ++) {
            if (intervals[i][0] < r) {
                ans ++;
                r = min(r, intervals[i][1]);
            } else {
                r = intervals[i][1];
            }
        }
        return ans;
    }
};

（贪心2）

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        sort(intervals.begin(), intervals.end());
        int n = intervals.size();
        int max_cnt = 1; // 无重复区间的最大数量
        int l = intervals[0][0], r = intervals[0][1];
        for (int i = 1; i < n; i ++) {
            if (intervals[i][0] >= r) {
                max_cnt ++;
                l = intervals[i][0];
                r = intervals[i][1];
            } else {
                r = min(r, intervals[i][1]);
            }
        }
        return n - max_cnt;
    }
};

用最少数量的箭引爆气球

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PK0OA5eq-1631977136456)(D:\github\gitee\leet-book-solutoin\动态规划\动规专题\动态规划之线性DP.assets\1631632209284.png)]$

本题是上一题的练习，但是需要将戳气球问题转换成为求无重复区间的数量。将一个气球的直径看成是一段区间，要用最少的弓箭数将所有的区间有覆盖到。那么其实重复区间可以使用一个弓箭即可，这就是利用贪心的思想。那么要使得弓箭覆盖到所哟的区间，就可以求出所有的无重复区间的数量，这样和无重复区间重叠的区间也就都被覆盖到了。

所以本题就转化为了求出区间的无重复区间数量，可以使用上题说的动规和贪心，但是由于动规会超时这里就不写了。

（贪心）

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        int n = points.size();
        sort(points.begin(), points.end());
        int l = points[0][0], r = points[0][1];
        int ans = 1;
        for (int i = 1; i < n; i ++) {
            if (points[i][0] > r) {
                ans ++;
                l = points[i][0];
                r = points[i][1];
            } else {
                r = min(r, points[i][1]);
            }
        }
        return ans;
    }
};

最长数对链

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tP1M794A-1631977136457)(D:\github\gitee\leet-book-solutoin\动态规划\动规专题\动态规划之线性DP.assets\1631672711322.png)]$

在一个线性的序列中，数组对之间满足某一种性质之后，可以进行线性的递推，所以本题还是可以使用LIS问题的思想来解决的。

当满足pair[i][0]大于pair[j][1]的时候（j < i），这就满足了数对链的条件，所以就可以将pair[i][0]放入数对链中。其实和求出上升子序列没有什么区别。只是我们将>的意义重新的定义了一遍而已。所以本题就是LIS问题。所以可以使用动规来解决。

（动规）

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        int n = pairs.size();
        sort(pairs.begin(), pairs.end());
        int ans = 0;
        vector<int> dp(n, 0);
        for (int i = 0; i < n; i ++) {
            dp[i] = 1;
            for (int j = 0; j < i; j ++) {
                if (pairs[i][0] > pairs[j][1]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

（贪心）

**如果换一个角度，可以将数对中的两个数，看成一段区间中的两个端点。这样其实就可以使用贪心的思想求出无重复的区间的数量问题。**这样可以进一步的降低时间复杂度。

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        int n = pairs.size();
        sort(pairs.begin(), pairs.end());
        int r = pairs[0][1];
        int ans = 1;
        for (int i = 1; i < n; i ++) {
            if (pairs[i][0] > r) {
                ans ++;
                r = pairs[i][1];
            } else {
                r = min(r, pairs[i][1]);
            }
        }
        return ans;
    }
};

（贪心右端点sort）

前面所有的类似求出无重复区间的问题，我们都是通过让区间的左端点排序，可以固定区间的一端，然后我们只需要比较另一端即可。

但是每一次我们发现了重叠的区间之后，需要更新区间的右端点，这里我们为了贪心的得到覆盖所有区间的范围，所以每一次尽量让区间的右端点都尽量的小，这样就可以留下更多的空间给剩下的区间。

其实可以在区间排序的时候，做一些手脚，就是我们既然知道每一次都要取右端点最小的区间。我们干脆直接将区间按右端点排序。如果是这样的是，如果不满足r < pairs[i][0]的情况下，就可以不用更新区间的右端点。因为已经将区间排好序了，所以从左向右区间的右端点就是从小到大的。

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        int n = pairs.size();
        sort(pairs.begin(), pairs.end(), [](auto& a, auto& b){
            return a[1] < b[1];
        });
        int r = INT_MIN;
        int ans = 0;
        for (int i = 0; i < n; i ++) {
            if (r < pairs[i][0]) {
                ans ++;
                r = pairs[i][1];
            }
        }
        return ans;
    }
};

最长字符串链

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Z4RBnq82-1631977136457)(D:\github\gitee\leet-book-solutoin\动态规划\动规专题\动态规划之线性DP.assets\1631676625013.png)]$

本题作为LIS问题最后一弹，可以作为最终的检验，是否真正地理解了LIS问题。

由题目可知，本题需要首先排序，使得单词的长度由小到大，这样可以方便地找出单词的前身。

然后的任务就是找到单词之间是否存在前身关系，如果满足单词之间的前身关系，那么当前的单词就是加入到前面一个单词列表之中。

所以本题就是LIS问题+如果判断一个字符串中包含了另一个字符串和任意一个字符。我们可以使用双指针的方法就可以很容易地判断是否有存在关系了。

（动规）

class Solution {
public:
    bool check(string& a, string& b) {
        bool flag = false;
        int pa = 0, pb = 0;
        while (pa < a.size()) {
            if (a[pa] != b[pb]) {
                if (flag) return false;
                pb ++;
                flag = true;
            } else {
                pa ++;
                pb ++;
            }
        }
        return true;
    }

    int longestStrChain(vector<string>& words) {
        int n = words.size();
        sort(words.begin(), words.end(),[](auto& a, auto& b){
            return a.size() < b.size();
        });

        vector<int> dp(n, 0);
        int ans = 0;
        for (int i = 0; i < n; i ++) {
            dp[i] = 1;
            for (int j = 0; j < i; j ++) {
                if (words[i].size() == words[j].size() + 1 && 
                    check(words[j], words[i])) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

（二）前后缀数组

除自身以外数组的乘积

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JrYswdkE-1631977136458)(D:\github\gitee\leet-book-solutoin\动态规划\动规专题\动态规划之线性DP.assets\1631687521387.png)]$

看到所有求出除了当前位置上的数之外，所有的数的乘积。其实最开始的想法一定都是直接将所有数先都乘起来，然后每一次都用所有数的乘积除以当前位置上的数即可。

但是有两个问题：1.当数组中出现0的时候，就不能使用。2.题目中规定了不能出现除法。

（动规）

所以我们可以想一些更暴力的方法，即遇到一个数的时候，可以计算出当前位置左边所有的数的乘积，然后计算出当前位置上右边所有数的乘积，最后左右两边的数再做一次乘积即可。

但是这样做的时间复杂度为O(N²)的，所以我们可以使用前后缀数组做一个优化，即left[i]记录0~i-1所有数的乘积，right[i]记录i + 1 ~ n - 1所有数的乘积。因为已经将每一个位置上左右两边的乘积都预处理了，所以最后只需要O(N)的时间复杂度就可以求出答案了，这就是典型的前后缀数组的空间换时间。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n), right(n);
        left[0] = 1;
        for (int i = 1; i < n; i ++) {
            left[i] = left[i - 1] * nums[i - 1];
        }
        right[n - 1] = 1;
        for (int i = n - 2; i >= 0; i --) {
            right[i] = right[i + 1] * nums[i + 1];
        }
        vector<int> ans;
        for (int i = 0; i < n; i ++) {
            ans.push_back(left[i] * right[i]);
        }
        return ans;
    }
};

（动规空间优化）

其实我们还可以在上面的基础上，去掉前后缀数组。就是使用vector<int> ans答案数组，充当前后缀数组的作用。

我们可以使用一个变量充当连续数字的乘积。即首先使用答案数组预处理出来左边的前缀乘积，然后再反向的在答案数组中再处理后缀乘积的时候，使用一个变量记录从后往前的乘积tmp，所以在循环到第i个位置的时候，tmp表示后i个数的乘积。此时dp[i] *= tmp就是左右两边的数组乘积相乘了。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n);
        dp[0] = 1;
        for (int i = 1; i < n; i ++) {
            dp[i] = dp[i - 1] * nums[i - 1];
        }
        int tmp = 1; // 记录第i个位置右边所有数的乘积
        for (int i = n - 2; i >= 0; i --) {
            tmp *= nums[i + 1];
            dp[i] *= tmp;
        }
        return dp;
    }
};

数组中的最长山脉

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-I2TddjnU-1631977136459)(D:\github\gitee\leet-book-solutoin\动态规划\动规专题\动态规划之线性DP.assets\1631694470682.png)]$

（动规枚举山顶）

一个山峰是由上坡和下坡组成的。所以直接暴力枚举每一个位置的左右两边的连续递增或者递减的数组即可。这就和前面一题处理前后缀乘积一样，需要先预处理一下前后缀和连续递增或者递减的数组，这样可以增加计算的效率。

如果arr[i] > arr[i - 1]那么prxfix[i] = prefix[i - 1] + 1，否则的话，pre[i]就等于1。同样的，后缀数组suffix的预处理也是一样。

最后ans = max(prefix[i] + suffix[i] - 1)即可，但是有一点需要注意，题目中需要的数组必须是有上坡和下坡的，所以当prefix[i]或者suffix[i]有一个是1的话，那么就不能构成山峰，所以就不能更新ans。

class Solution {
public:
    int longestMountain(vector<int>& arr) {
        int n = arr.size();
        // 预处理前后缀数组
        vector<int> prefix(n, 1);
        for (int i = 1; i < n; i ++) {
            if (arr[i] > arr[i - 1]) {
                prefix[i] = prefix[i - 1] + 1;
            }
        }
        vector<int> suffix(n, 1);
        for (int i = n - 2; i >= 0; i --) {
            if (arr[i] > arr[i + 1]) {
                suffix[i] = suffix[i + 1] + 1;
            }
        }

        int ans = 0;
        for (int i = 0; i < n; i ++) {
            // 如果prefix或者suffix中有一个是1的话说明不能形成山峰
            if (prefix[i] > 1 && suffix[i] > 1) 
                ans = max(ans, prefix[i] + suffix[i] - 1);
        }
        return ans >= 3 ? ans : 0;
    }
};

（枚举山脚）

因为本题中的山峰数组是连续的山峰，所以可以枚举山脚，然后顺着山脚枚举到山峰，最后在从山峰下到山脚。这样枚举山脚的方式就是在勾勒出整个山峰。

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-x5DxNBxV-1631977136459)(D:\github\gitee\leet-book-solutoin\动态规划\动规专题\动态规划之线性DP.assets\1631698120410.png)]$

class Solution {
public:
    int longestMountain(vector<int>& arr) {
        int n = arr.size();
        int i = 1;
        int ans = 0;
        while (i < n) {
            int up = 0, down = 0;
            while (i < n && arr[i] > arr[i - 1]) i ++, up ++;
            while (i < n && arr[i] < arr[i - 1]) i ++, down ++;
            if (up > 0 && down > 0)
                ans = max(ans, up + down + 1);
            while (i < n && arr[i] == arr[i - 1]) i ++;
        }
        return ans >= 3 ? ans : 0;
    }
};

接雨水

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fSYiH0ue-1631977136460)(D:\github\gitee\leet-book-solutoin\动态规划\动规专题\动态规划之线性DP.assets\1631699054365.png)]$

（动规-前后缀数组）

如果想要形成雨水的话，就要形成低洼的地方，所以最暴力的方法就是枚举每一个位置左右两边的最大的柱子的高度。（注意：是左右两边的最大高度，不是离得最近的两个高度，因为要一次性地算出一个位置上能接的所有雨水，一定是从全局的角度看，而不是只看最近的高度。）

这种暴力的方法，我们知道可以使用前后缀数组来优化，所以使用两个数组r[i], l[i]表示第i个位置上的左右两边的最大高度，最后的答案就是ans += h - min(l[i], r[i])。

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> l(n), r(n);
        for (int i = 1; i < n; i ++) {
            l[i] = max(l[i - 1], height[i - 1]);
        }
        for (int i = n - 2; i >= 0; i --) {
            r[i] = max(r[i + 1], height[i + 1]);
        }
        int ans = 0;
        for (int i = 1; i < n - 1; i ++) {
            int h = min(l[i], r[i]);
            if (h > height[i]) {
                ans += h - height[i];
            }
        }
        return ans;
    }
};

（双指针）

根据木桶原理，水量是由最短的木板决定的，所以我们就可以关注短木板一段的水量即可。

为了一次性找出一个位置上的所有蓄水量，所以我们使用两个指针指向两个木板，并且两个指针是分别指向两端的。

然后我们需要两个变量lMax和rMax来记录左边和右边的最大高度。如果不足最大的高度，那么椴木板就可以形成低洼，如果当前的木板比对应边的最大高度要高，那就不能形成低洼处，我们就要更新对应边的木板最大高度。

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int lMax = 0, rMax = 0;
        int l = 0, r = n - 1;
        int ans = 0;
        while (l < r) {
            if (height[l] < height[r]) {
                if (lMax > height[l]) {
                    ans += lMax - height[l];
                } else {
                    lMax = height[l];
                }
                l ++;
            } else {
                if (rMax > height[r]) {
                    ans += rMax - height[r];
                } else {
                    rMax = height[r];
                }
                r --;
            }
        }
        return ans;
    }
};

（三）经典问题

*环形子数组的最大和

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AgzXAtGT-1631977136460)(D:\github\gitee\leet-book-solutoin\动态规划\动规专题\动态规划之线性DP.assets\1631777352533.png)]$

（最小/最小子数组和）

在一个数组求出最大的子数组的和起前面已经解决了，本题的区别在于头尾部的子数组可以跨越中间的数组，然后求出最大子数组的和。

所以我们这里就多加了一种情况，第一种就是最大的子数组和在原数组的中间部分，第二种是最大子数组和在原数组有原数组的头尾两端构成。

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JXGYBQlj-1631977136460)(D:\github\gitee\leet-book-solutoin\动态规划\动规专题\动态规划之线性DP.assets\1631782791888.png)]$

第一种情况就是最大子数组和那一道题。

第二种情况看起来就不太好求了，但是我们可以换一个思路，如果头尾数组和最大，那么我们只需要使得sum - 中间部分的数组和，那么就是要让中间部分的数组和最小，这不就转化为了求出整个数组的最小子数组和么。

所以我们就可以在递推的时候，将数组中的最大最小子数组和都求出来，最后的答案就是max(maxVal, sum - minVal)。但是要注意的是，如果整个数组都是负数，那么sum - minVal就是0了，而maxVal一定是一个负数，所以这个时候应该去maxVal而不是sum-minVal（也就是0）。所以我们需要特判，如果maxVal < 0那么说明整个数组都是负数，这时直接返回maxVal即可。

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();
        int sum = nums[0]; // 数组中所有数的和
        vector<int> minDp(n), maxDp(n);
        int minVal = nums[0], maxVal = nums[0];// 最大/最小子数组和
        minDp[0] = nums[0], maxDp[0] = nums[0];// 初始化dp数组

        for (int i = 1; i < n; i ++) {
            sum += nums[i];
            minDp[i] = min(nums[i], nums[i] + minDp[i - 1]);
            minVal = min(minVal, minDp[i]);
            maxDp[i] = max(nums[i], nums[i] + maxDp[i - 1]);
            maxVal = max(maxVal, maxDp[i]);
        }

        if (maxVal < 0) return maxVal; // 如果数组中的数都为负数,则返回maxVal
        return max(maxVal, sum - minVal);
    }
};

（动规 + 空间优化）

因为最大/最小子数组和的递推公式是dp[i - 1]转移到dp[i]的，所以可以使用两个变量来做空间优化。

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();
        int sum = nums[0]; // 数组中所有数的和
        int minDp = nums[0], maxDp = nums[0];
        int minVal = nums[0], maxVal = nums[0];// 最大/最小子数组和

        for (int i = 1; i < n; i ++) {
            sum += nums[i];
            minDp = min(nums[i], nums[i] + minDp);
            minVal = min(minVal, minDp);
            maxDp = max(nums[i], nums[i] + maxDp);
            maxVal = max(maxVal, maxDp);
        }

        if (maxVal < 0) return maxVal; // 如果数组中的数都为负数,则返回maxVal
        return max(maxVal, sum - minVal);
    }
};

（单调队列+前缀和）

当解决「环形的数组」的问题的时候，我们通常的办法都是「破环成链」。即环形数组就是两个相同的数组组合而成，那么我们可以将两个相同的数组拉成一条链状结构。

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xkTFSRtY-1631977136461)(D:\github\gitee\leet-book-solutoin\动态规划\动规专题\动态规划之线性DP.assets\1631782320756.png)]$

当环形的数组变成了线性的数组的时候，我们就是可以使用递推的方式来求解子数组的和了。

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();
        vector<int> sum(2 * n + 1);
        // 处理前缀和
        for (int i = 1; i <= 2 * n; i ++) {
            sum[i] = sum[i - 1] + nums[(i - 1) % n];
        }

        deque<int> q;
        // 虚拟节点
        q.push_back(0); 
        int ans = INT_MIN;
        for (int i = 1; i <= 2 * n; i ++) {
            // 维护窗口中元素的有效性
            if (!q.empty() && i - n > q.front()) q.pop_front(); 
            // 更新答案
            ans = max(ans, sum[i] - sum[q.front()]);  
            // 保持窗口中元素的单调性
            while (!q.empty() && sum[q.back()] >= sum[i]) q.pop_back();
            q.push_back(i);
        }
        return ans;
    }
};

*乘积最大子数组

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gzhF8Sxk-1631977136461)(D:\github\gitee\leet-book-solutoin\动态规划\动规专题\动态规划之线性DP.assets\1631785605346.png)]$

（暴力）

最暴力的方法就是将所有的子序列都枚举一遍，因为最终要求得最大的子数组一定是连续的，所以可以使用n²的时间复杂度就会算出来了。

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        int ans = INT_MIN;
        for (int i = 0; i < n; i ++) {
            int tmp = 1;
            for (int j = i; j >= 0; j --) {
                tmp *= nums[j];
                ans = max(ans, tmp);
            }
        }
        return ans;
    }
};

（动规）

本题乍一眼看起来其实是很像「最大子数组和」那一道题目的，但是仔细一想，对于乘法来说，可能当前位置是一个负数，但是由于下一个数也是负数，这时候反而希望负数越小越好，这样最终的乘积才会更大。所以根据这一点，所以我们需要同时保存一个乘积过后的最大值和一个乘积过后的最小值。

1.状态定义

maxDp[i]表示以第i个位置为结尾的最大数组乘积，minDp[i]表示以第i个位置结尾的最小数组乘积。

2.递推公式

根据nums[i]的正负号，我们可以分出两种情况：

1.如果nums[i] >= 0的话，maxDp[i] = maxDp[i - 1] * nums[i]，minDp[i] = minDp[i - 1] * nums[i]，最后maxDp[i]和minDp[i]要和nums[i]本身再比较一下，得出递推公式nums[i] = max(maxDp[i - 1] * nums[i], nums[i])，nums[i] = min(minDp[i - 1] * nums[i], nums[i])。

2.同样的，如果nums[i] < 0，maxDp[i] = max(nums[i] * minDp[i - 1], nums[i]);，minDp[i] = min(nums[i] * maxDp[i - 1], nums[i]);。

3.初始化

根据递推公式，我们需要从1开始遍历，所以需要初始化minDp[0] = nums[0]和maxDp[0] = nums[0]。

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

（动规+空间优化）

我们发现dp数组在递推的过程中，每一个状态只由前一个状态递推出来，所以可以使用滚动数组的形式循环地使用数组，这样就可以省去O(N)的空间。

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        int minDp = nums[0], maxDp = nums[0];
        int ans = nums[0];
        for (int i = 1; i < n; i ++) {
            if (nums[i] > 0) {
                maxDp = max(nums[i] * maxDp, nums[i]);
                minDp = min(nums[i] * minDp, nums[i]);
            } else {
                int tmp = maxDp;
                maxDp = max(nums[i] * minDp, nums[i]);
                minDp = min(nums[i] * tmp, nums[i]);
            }
            ans = max(ans, maxDp);
        }
        return ans;
    }
};

（动规空间优化的简洁写法）

其实每一次状态转移只有三种情况，所以我们可以不用分出nums[i]到底是大于0还是小于0，可以直接将三种状态直接转移即可。

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        int ans = nums[0];
        int minVal = nums[0], maxVal = nums[0];
        for (int i = 1; i < n; i ++) {
            int ta = maxVal, ti = minVal;
            maxVal = max(max(nums[i], ta * nums[i]), ti * nums[i]);
            minVal = min(min(nums[i], ti * nums[i]), ta * nums[i]);
            ans = max(ans, maxVal);
        }
        return ans;
    }
};

矩阵的最大非负积

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-aEZXp8sh-1631977136462)(D:\github\gitee\leet-book-solutoin\动态规划\动规专题\动态规划之线性DP.assets\1631844050631.png)]$

（动规）

和上一道题目类似，因为是乘积的最值，所以会出现负数乘以负数反而变大的情况，因此我们需要同时记录当前路径下可以达到的最大值和最小值。

1.状态定义

minDp[i][j]表示从(0,0)到(i,j)路径上的最小乘积，maxDp[i][j]表示从(0,0)到(i,j)路径上的最小乘积。

2.递推公式

对于nums[i]的正负，分成两种情况。

如果nums[i] >= 0，正数乘以大数=大数，正数乘以小数=小数。所以maxDp[i][j] = max(maxDp[i - 1][j], maxDp[i][j - 1]) * grid[i][j];,minDp[i][j] = min(minDp[i - 1][j], minDp[i][j - 1]) * grid[i][j];。

如果nums[i] < 0，负数乘以大数=小数，负数乘以小数=大数。所以maxDp[i][j] = min(minDp[i - 1][j], minDp[i][j - 1]) * grid[i][j];，minDp[i][j] = max(maxDp[i - 1][j], maxDp[i][j - 1]) * grid[i][j];。

3.初始化

根据递推公式，第一行和第一列的路径上的最大最小值只有一个方向可以递推，所以需要手动的初始化。

要注意的是：和上一道题目不同的是本题求的是路径上的最值乘积，和子数组中的连续最值乘积是不同的。这里的状态转移只能是从上或者从左转移过来的，而自己本身不是一个状态，所以就不能从中间的路径断开。

在上一题中因为连续的子数组乘积所以自己本身也是一个状态，所以可以从数组中的中间提取出子数组的乘积作为答案，所以即使是线性的递推，但是还是可以每一个位置都有不同的最大最小值。

class Solution {
public:
    const int mod = 1e9 + 7;
    using LL = long long;
    int maxProductPath(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<LL>> maxDp(n, vector<LL>(m));
        vector<vector<LL>> minDp(n, vector<LL>(m));
        minDp[0][0] = maxDp[0][0] = grid[0][0];
        for (int i = 1; i < n; i ++) {
            minDp[i][0] = maxDp[i][0] = maxDp[i - 1][0] * grid[i][0];
        }
        for (int i = 1; i < m; i ++) {
            minDp[0][i] = maxDp[0][i] = maxDp[0][i - 1] * grid[0][i];
        }
        for (int i = 1; i < n; i ++) {
            for (int j = 1; j < m; j ++) {
                if (grid[i][j] >= 0) {
                    maxDp[i][j] = max(maxDp[i - 1][j], maxDp[i][j - 1]) * grid[i][j];
                    minDp[i][j] = min(minDp[i - 1][j], minDp[i][j - 1]) * grid[i][j];
                } else {
                    maxDp[i][j] = min(minDp[i - 1][j], minDp[i][j - 1]) * grid[i][j];
                    minDp[i][j] = max(maxDp[i - 1][j], maxDp[i][j - 1]) * grid[i][j];
                }
            }
        }
        return maxDp[n - 1][m - 1] < 0 ? -1 : maxDp[n - 1][m - 1] % mod;
    }
};

摆动序列

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vTCfNhj1-1631977136462)(D:\github\gitee\leet-book-solutoin\动态规划\动规专题\动态规划之线性DP.assets\1631848199283.png)]$

（动规）

本题很像「最长上升子序列」，但是有一个很不一样的地方就是：最长上升子序列不具有连续的传递性，而最长摆动序列有。比方说：1,3,5,2,9，如果求出摆动序列的长度的话，当考虑9的时候，我们需要考虑9的前面是5的情况，而是直接考虑9的前面是2的情况即可，因为2的前面是5，所以在2这个地方的转折一定会被算进2所在的摆动序列当中，所以在计算以9结尾的数字的时候，可以直接考虑2和9的大小情况即可。、

所以在递推公式判断的时候，我们只需要判断nums[i]和nums[i - 1]的情况即可，递推摆动序列的长度。

1.状态定义

up[i]表示以i结尾并且在i这个点上升的摆动序列的长度。down[i]表示以i结尾并且在i这个位置下降的摆动序列的长度。

2.递推公式

如果nums[i] > nums[i - 1]，那么说明序列在上升，所以up[i] = max(up[i - 1], down[i - 1] + 1)。

如果nums[i] < nums[i - 1]，那么说明序列在下降，所以down[i] = max(down[i - 1], up[i - 1] + 1)。

3.初始化

因为每一个位置都可以成为一个序列，所以dp可以全部初始化为1。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        vector<int> up(n, 1), down(n, 1);
        int ans = 1;
        for (int i = 1; i < n; i ++) {
            if (nums[i] > nums[i - 1]) {
                up[i] = max(up[i - 1], down[i - 1] + 1);
                down[i] = down[i - 1];
            } else if (nums[i] < nums[i - 1]) {
                down[i] = max(down[i - 1], up[i - 1] + 1);
                up[i] = up[i - 1];
            } else {
                up[i] = up[i - 1];
                down[i] = down[i - 1];
            }
            ans = max({ans, up[i], down[i]});
        }
        return ans;
    }
};

（动规空间优化）

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        int up = 1, down = 1;
        for (int i = 1; i < n; i ++) {
            if (nums[i] > nums[i - 1]) {
                up = down + 1;
            } else if (nums[i] < nums[i - 1]) {
                down = up + 1;
            }
        }
        return max(up, down);
    }
};

（贪心）

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-l4KN57Ii-1631977136463)(D:\github\gitee\leet-book-solutoin\动态规划\动规专题\动态规划之线性DP.assets\1631850225994.png)]$

每一个点都是一个数字，我们可以贪心地想要使得摆序列的长度更大，所以需要将摆动序列的峰值上下落差大。因为这样落在摆动的过程中的点才可以更多。

如果我们不取最大值为摆动序列的极值点，那么摆动序列中的可能出现的峰值就会越小，这样出现摆动的机会就会越小。所以要取最大/最小值当做摆动序列的峰值。

注意：前后相同的数字是不能构成摆动序列的，所以我们需要先对数组中的数字去重。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        nums.erase(unique(nums.begin(), nums.end()), nums.end());
        int n = nums.size();
        if (n <= 2) return n;
        int ans = 2;// 默认头尾节点一定在摆动序列当中
        for (int i = 1; i < n - 1; i ++) {
            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) ans ++;
            if (nums[i] < nums[i - 1] && nums[i] < nums[i + 1]) ans ++;
        }
        return ans;
    }
};