力扣 | 递增子序列 | 动态规划 | 最长递增子序列、最长递增子序列的个数、及其变式

最长递增子序列：原序-递增数值问题
最长定差子序列：原序-定差数值问题
最长数对链：非原序-递增区间问题
俄罗斯信封套娃：非原序-递增二维数值问题

一、300. 最长递增子序列

LeetCode：300. 最长递增子序列

一个很容易的解法，就是定义$dp[i]$表示以第$i+1$个数字结尾的最长递增子序列长度，要求出这个长度，只需要往前遍历一次，看看前面有没有比它小的字符，这样就可以构成一个递增子序列。那么对于第$i+1$个字符而言，将它之前的所有数字遍历一遍可以求出最长递增子序列。
时间复杂度：$O(n^2)$

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

不过我们知道要求出$dp[i]$只需要找到前面比它小的数字即可。

我们可以动态维护一个最长递增序列，这样序列是这样的，$list[i]$表示当前长度为$i+1$的递增子序列的末尾的最小数字。我们可以动态维护这样的数据结构。

• 当我们考虑$dp[i]$时，我们可以通过$list$来快速求出$dp[i]$的值（二分查找）。因为$list$是按递增子序列长度排列的，并且每一个长度都维护了一个最小值。
• 对于第$i+1$个数字，看它的递增长度$len$ 来与$list[len]$对比，维护$list$

时间复杂度：$O(nlogn)$

class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int> lst;for(int i = 0; i < nums.size(); ++ i){int left = 0, right = (int) lst.size() - 1, mid;while(left <= right){//二分查找，查找小于nums[i]的最大值mid = (right - left) / 2 + left;if(lst[mid] >= nums[i]){right = mid - 1;}else left = mid + 1;}if(left == lst.size()) lst.emplace_back(nums[i]);if(lst[left] > nums[i]) lst[left] = nums[i];}return lst.size();}
};

二、673. 最长递增子序列的个数

LeetCode：673. 最长递增子序列的个数

这个题难度大很多！我们无法直接使用二分查找！因为我们维护的递增子序列是最小值！即使记录每个位置现在的个数也无法进行状态转移呀！ 比如[1, 5 , 2 , 3]，这里我们维护了[1, 5]作为长度为2的，现在我们加入2，现在长度为2变成了[1,2]，但我们并不能说长度为2的有两个，这样加入3的时候，一共有两个长度为3的序列，[1,2,3]。原因就在于我们维护的递增子序列每次都是最小的，后面加入的更长并不一定前面更小的都能和他构成更长的

那我们先考虑直接暴力计算的方法吧！

我们不构造，直接二维循环。我们仍然使用$dp[i]$表示第$i+1$个数字为尾部的最长递增子序列；我们使用$cnt[i]$表示第$i+1$个数字为尾部的最长递增子序列的个数。
时间复杂度：$O(n^2)$

class Solution {
public:int findNumberOfLIS(vector<int>& nums) {vector<int> dp(nums.size(), 1);vector<int> cnt(nums.size(), 1);int mx = 1;int ans = 0;for(int i = 0; i < nums.size(); ++ i){for(int j = i - 1; j >= 0; -- j){if(nums[i] > nums[j]){if(dp[j] + 1 > dp[i]){dp[i] = dp[j] + 1;cnt[i] = cnt[j];}else{if(dp[j] + 1 == dp[i]){cnt[i] += cnt[j];}}}}if(dp[i] == mx){ans += cnt[i];}else{if(dp[i] > mx) mx = dp[i], ans = cnt[i];}}return ans;}
};

高阶思路：
对于300. 最长递增子序列的解法二，我们维护的一个标准的最小值。

如果我们能想到另外一点就太强了：

• 我们每次去替换$list[i]$实际上都是当前值$val$比$list[i]$小，那么我们换一个想法，我们不去替换它，而是将$list[i]$扩展为一个数组，想替换最小值变为它加在这个数组的末尾，这样我们就能够保证，每次加入一个$val$都能保证$list[i]$是单调非增的。而且跟我们不看数组的所有元素，只看最末尾的元素的话，实际上和300. 最长递增子序列一样，所以我们能够保证每次加入的是正确的位置。
• 这样做，我们就知道，我们考虑任何一个数$val$时，它如果放在$list[i]$处，我们能够知道它能构成多少个长度为$i+1$的递增子序列，这个数量这跟$list[i-1]$有关，而且在$list[i-1]$的数都出现在$val$之前，所以一定是可以进行状态转移的。

时间复杂度：$O(nlogn)$

class Solution {int binarySearch(int n, function<bool(int)> f) {int l = 0, r = n;while (l < r) {int mid = (l + r) / 2;if (f(mid)) {r = mid;} else {l = mid + 1;}}return l;}public:int findNumberOfLIS(vector<int> &nums) {vector<vector<int>> d, cnt;for (int v : nums) {int i = binarySearch(d.size(), [&](int i) { return d[i].back() >= v; });int c = 1;if (i > 0) {int k = binarySearch(d[i - 1].size(), [&](int k) { return d[i - 1][k] < v; });c = cnt[i - 1].back() - cnt[i - 1][k];}if (i == d.size()) {d.push_back({v});cnt.push_back({0, c});} else {d[i].push_back(v);cnt[i].push_back(cnt[i].back() + c);}}return cnt.back().back();}
};

---

以下问题我们只谈他们使用最长递增子序列的方式解决的方法。这里并不是说要你记住这个方法，而是理解他们为什么能这样用，扩展思维。

三、变式

1、646. 最长数对链

LeetCode：646. 最长数对链

这个问题最快速和方便是使用贪心算法，不过我们也可以线排序 然后像最长递增子序列一样，使用时间复杂度为$O(n^2)$的动态规划。

贪心算法的证明：

对于任何一个数对链，首先对于任何一个维度，都是递增的；其次它构成的链也是递增的。我们来考察数对链中的其中任何一个数对，如果我们能找到满足要求的更小的数对（任何一维更小或者两维都能小），那么我可以将其替换。根据这个原因，我们可以将第二维排序，另一维按最小能满足条件的值来进行选择。
实际上将其映射到数轴上，可以发现我们最好选择两端都更小的且满足要求的，这样不会因为右端更大而导致有一些重叠不能选。这也是为什么我们每次都选择最小，而不选择一端大一端更小的。

2、1218. 最长定差子序列

1218. 最长定差子序列

这个题也一样直接像最长递增子序列一样，使用时间复杂度为$O(n^2)$的动态规划。

当然为什么最长对数链需要排序，而他们不要？ 因为他们求的是子序列顺序已经固定了。而最长对数链有两维，必须满足其中一维满足要求才能用这种动态规划方式。

但是不得不说这个题和最长递增子序列的区别是什么：

• 最长递增子序列的关系是增，而这里的关系是差difference
• 确定一个数val，无法在最长递增子序列中确定它是哪一个，而这里可以确定它的前驱是val - difference。这样就可以引入哈希查找了！将$O(n^2)$降为$O(n)$

class Solution {
public:int longestSubsequence(vector<int>& arr, int difference) {unordered_map<int, int> mp;//以mp[i]结尾的最长递增子序列int mx = 1;for(int i = 0; i < arr.size(); ++ i){if(mp.count(arr[i] - difference) == 0){mp[arr[i]] = 1;}else{mp[arr[i]] = mp[arr[i] - difference] + 1;}mx = max(mx, mp[arr[i]]);}return mx;}
};

由于数字就那么大，使用数组进行存储比哈希表更快。但是我们需要注意一些问题：

• $-10^4<=arr[i],difference<=10^4$，那么将其映射到正数里是$[0,2\times 10^4]$，千万别认为是$[0,10^8]$，两边同时加上$10^4$，是两倍关系不是指数关系。
• 注意$arr[i]-difference$的取值范围是：$[-2\times 10^4,2\times 10^4]$，所以得开的数组范围是$[0,4\times 10^4]$

class Solution {
public:int longestSubsequence(vector<int>& arr, int difference) {int mx = 1;array<int, 40000 + 1> mp = {};for(int i = 0; i < arr.size(); ++ i){mp[arr[i] + 20000] = mp[arr[i] - difference + 20000] + 1;mx = max(mx, mp[arr[i] + 20000]);}return mx;}
};

3、1027. 最长等差数列

LeetCode：1027. 最长等差数列

这一题和之前的区别在于，等差的大小是不知道的，我们不能拿着一个数就确定我们需要的他的最长等差长度，因为这跟等差的大小有关，因此我们定义$dp[i][d]$表示以i结尾的等差为d的最长长度，我们只需要遍历d就能像最长定差子序列一样求解问题了。

不过我们需要注意两个问题：

• 定义array时需要特别注意顺序，二维越界不一定会出错，容易混淆顺序
• 等差有正的有负的，因此等差的范围为$[-500,500]$，并且当一个数没有这样的等差值时，它自己当做等差数列，因此长度为1。

class Solution {
public:int longestArithSeqLength(vector<int>& nums) {array<array<int, 1001>, 501> dp = {};//注意定义的顺序，不如直接int dp[501][1001];int mx = 1;for(int i = 0; i < nums.size(); ++ i){for(int d = -500; d <= 500; ++ d){//等差的值if(nums[i] - d < 0 || nums[i] - d > 500) dp[nums[i]][d + 500] = 1;//当一个数没有这样的等差值时，它自己当做等差数列，因此长度为1else dp[nums[i]][d + 500] = dp[nums[i] - d][d + 500] + 1;mx = max(dp[nums[i]][d + 500], mx);}}return mx;}
};

4、354. 俄罗斯套娃信封问题

LeetCode：354. 俄罗斯套娃信封问题

乍一看这个题目好像跟LeetCode：646. 最长数对链一毛一样，最长对数链使用贪心能够解决，难道这道题也可以？答案是不可以，原因在于，信封一端更小，但另一端可能很大导致其他信封塞不下。

最长对数链之所以右端更小就更好的原因在于，它不会影响比它大的数对的选择，选择更大的可能这个更大的区间中间可以放多个，选择右端最小就不会有这样的问题 即右端优先。但信封任何一端都没有这样的优先权，两端是等价的。

这个题和数对链一样，它们不是子序列的问题，直接二重循环是不行的。我们必须知道本质，能变成子序列问题是因为，答案必然由“子序列”构成，而不能是其他的顺序。

那我们如果使用二重循环，那就需要保证问题的解是子序列，我们需要从答案中考虑：

• 答案保证了w和h是单增的，那么我们在数组中尝试让w单增，那么选择时 答案是否就是这个子序列了呢？（很难想到吧）
• 官解告诉我们，并不是，原因在于当w存在相等的值时，我们仅仅看h的大小会有问题，实际上这些信封都不能套起来，因此我们需要保证w相同时，不会导致只考虑h出现问题。这里有两种方式：
  • ①保证w相同时，h是降序，这样单考虑h构成的子序列不会出现把相同的宽度套在一起的情况。
  • ②我们再来考虑一下w，相同w的信封不被套起来。

信封套娃实际上可以转化为二维最长递增子序列的问题。
我们这样就发现了问题的本质：
（1）使用从前往后遍历的方式来查看当前值和之前值能构成的答案时，实际上就必须保证解是子序列。无论是维护答案还是二重循环。
（2）从答案中思考问题的结构，答案必须保证升序。因此将二维中的一维升序转换后，实际上答案必然就在转换后的子序列中（原因是答案必然是其中一维升序！这是非常神奇的点）

使用二重循环的方法：实际上将其中一维升序之后，就变成了最长递增子序列的问题。不作第二维处理就剔除一下升序那维相同的情况即可。

使用二分查找的方法：仅仅将其中一维升序不够，因为第二维放的位置是跟大小有关系的，无法做到通过另一维判断情况。那么为了保证一维相同时的情况不会被考虑，我们得对相同时的情况的另一维做处理。 我们要刨除相同一维的影响，直接使得另一维不可能构成答案，应该怎么做？ 正确的做法是在保证一维升序的情况下，另一维降序，这样的话单独考虑这些宽度相同的信封时，他们不可能在子序列的情况下构成嵌套关系。 这样的话就一定不会出现导致相同宽度的信封被认为嵌套。

方法一： 二重循环
时间复杂度：$O(n^2)$ 超时

不用二维降序，多加一个判断就好：

bool cmp(vector<int> & a, vector<int> & b){return a[0] < b[0];
}
class Solution {
public:int maxEnvelopes(vector<vector<int>>& envelopes) {sort(envelopes.begin(), envelopes.end(), cmp);vector<int> dp(envelopes.size(), 1);int mx = 1;for(int i = 1; i < envelopes.size(); ++ i){for(int j = i - 1; j >= 0; -- j){if(envelopes[i][0] != envelopes[j][0] && envelopes[i][1] > envelopes[j][1]){dp[i] = max(dp[i], dp[j] + 1);mx = max(mx, dp[i]);}}}return mx;}
};

使用二维降序，直接就变成了最长递增子序列的问题：

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

方法二： 启发式排序 + 二分查找
时间复杂度：$O(nlogn)$

bool cmp(vector<int> & a, vector<int> & b){if(a[0] == b[0]) return a[1] > b[1];return a[0] < b[0];
}
class Solution {
public:int maxEnvelopes(vector<vector<int>>& envelopes) {sort(envelopes.begin(), envelopes.end(), cmp);int n = envelopes.size();vector<int> lst;for(int i = 0; i < n; ++ i){auto it = lower_bound(lst.begin(), lst.end(), envelopes[i][1]);//寻找大于等于的第一个位置,不要用upper因为等于也是不行的if(it == lst.end()){lst.emplace_back(envelopes[i][1]);}else{*it = min(*it, envelopes[i][1]);}}return (int) lst.size();}
};

方法三： 单维排序 + 二分查找
时间复杂度：$O(nlogn)$，虽然运行过慢，但实际上就是$O(nlogn)$，慢的原因是判断的条件多了很多，空间大了一些。

这种方法官解没有提供（不是想拓展一下思路深度思考的，别看了，判断写的太长了，条件有点多）

还可以观察到一个有意思的事情，由于相同w的信封是按顺序排列的，那我们一定会按顺序进行考虑，我们什么时候会出现错误的情况呢？
我们来考虑在求 最长递增子序列的个数时， 我们维护一个最长递增子序列 并维护每个位置有哪些数。对于相同宽度的信封$e1,e2,e3,e4$（从小到大排序，即$e1<e2<e3<e4$，对于当前维护的信封$m1,m2,m3,m4,m5$，如果将$ei$替换$m1$ ~ $m4$中的任何一个信封，不管$ei$怎么替换最长长度都是对的，我们可以会替换成$e1,e2,e3,e4,m5$，这个时候我们随便举个例子$e4$的位置，代表的是以$e4$结尾的能构成长度为4的套娃！但实际上能行吗？ 如果有这样的情况$m2<e3<e4<m3<m4$，我们说当$e3$替换掉$m3$之后，$e4$被认为放到$m4$的位置，这是对的嘛？显然是不对的，$e4$根本无法构成更长的，所以出现错误。
如果我们同样来维护每个位置有哪些信封，这个时候你必须用$e4$和$e3$的位置里的所有信封进行比较，如果存在一个使得比$e4$更小（实际上只需要比一次），那么$e4$可以替换$m4$，如果不存在，那么$e4$需要被抛弃，因为它的作用不及$e3$。
但如果是这样的，我们考虑$m1<e3<m2<m3<e4<m4$，这个时候又是什么情况？ $m2$一定被$e3$替换，$e4$是否一定能替换$m4$？答案是一定的！因为即使没有$e3$的存在，$e4$也一定能替换$m4$，有了并不影响，这样我们就可以写出一个新算法！并不需要第二维排序了，多加一个判断就行。（空间复杂度稍微高了一点点）
虽然我们知道有了个新方法，但是别忘了官解最好是第二维降序！这样就不会出现这样的问题了，因为这样第一维相同，第二维不可能构成答案了！

bool cmp(vector<int> & a, vector<int> & b){/*if(a[0] == b[0]) return a[1] < b[1];*/return a[0] < b[0];
}
class Solution {
public:int maxEnvelopes(vector<vector<int>>& envelopes) {sort(envelopes.begin(), envelopes.end(), cmp);vector<vector<vector<int>>> lst;for(int i = 0; i < envelopes.size(); ++ i){int left = 0, right = (int) lst.size() - 1, mid;while(left <= right){mid = (right - left) / 2 + left;if(lst[mid].back()[1] < envelopes[i][1]){left = mid + 1;}else{right = mid - 1;}}//right left,left是需要放的地方if(right == -1 || lst[right].back()[0] != envelopes[i][0]){//与前一个位置的最后一个信封宽度不相同：直接放就行if(left == lst.size()){lst.push_back({envelopes[i]});}else {if(lst[left].back()[0] == envelopes[i][0]){//考虑当前位置的最后一个是否和当前位置最后一个信封宽度相同，相同用小的替代if(lst[left].back()[1] > envelopes[i][1]){lst[left].back() = envelopes[i];}}else lst[left].emplace_back(envelopes[i]);}}else{//与前一个位置的最后一个信封宽度相同if(lst[right].size() >= 2){//前一个位置的信封至少要有两个才行 有一个肯定不能放if(lst[right][(int) lst[right].size() - 2][1] < envelopes[i][1])//有两个，看看是否能放if(left == lst.size()){lst.push_back({envelopes[i]});}else {if(lst[left].back()[0] == envelopes[i][0]){if(lst[left].back()[1] > envelopes[i][1]){lst[left].back() = envelopes[i];}}else lst[left].emplace_back(envelopes[i]);}}}}return lst.size();}
};

5、1964. 找出到每个位置为止最长的有效障碍赛跑路线

这个题实际上就是维护最长来使用二分查找的最长递增子序列的问题。唯一区别就是可以相同，相当于最长非减子序列。

class Solution {
public:vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {vector<int> lst;vector<int> ans;int n = obstacles.size();for(int i = 0; i < n; ++ i){auto it = upper_bound(lst.begin(), lst.end(), obstacles[i]);if(it == lst.end()){lst.emplace_back(obstacles[i]);ans.emplace_back(lst.size());}else{*it = min(*it, obstacles[i]);ans.emplace_back(it - lst.begin() + 1);}}return ans;}
};