Code-1.31-子序列问题

leetcode.cn/problems/longest-increasing-subsequence/" rel="nofollow">300. 最长递增子序列

题目分析

1. 状态表示

dp[i]表示：以i结尾的所有子序列中，最长递增子序列的长度。

2. 状态转移方程

• dp[i]
  • 长度为1 -> 1
  • 长度大于1 -> nums[j] < nums[i] -> max(dp[j] + 1)

3. 初始化

把表里所有值初始化为1。

4. 填表顺序

从左往右。

5. 返回值

dp表中的最大值。

代码实现

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

leetcode.cn/problems/wiggle-subsequence/" rel="nofollow">376. 摆动序列

分析：用多状态dp表完成。

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int n = nums.size();if (n == 1) return 1;if (n == 2 && nums[0] != nums[1]) return 2;vector<int> f(n, 1), g(n, 1); // f表示最后一个数位较小的数的摆动序列的最长子序列的长度，g表示较大的。int ret = 0;for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[i] < nums[j]) f[i] = max(g[j] + 1, f[i]);if (nums[i] > nums[j]) g[i] = max(f[j] + 1, g[i]);}ret = max(max(f[i], g[i]), ret);}return ret;}
};

leetcode.cn/problems/number-of-longest-increasing-subsequence/" rel="nofollow">673. 最长递增子序列的个数

分析：想快速得到个数，需要再添加一个辅助计数的数组。

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

leetcode.cn/problems/maximum-length-of-pair-chain/" rel="nofollow">646. 最长数对链

分析：先排序再做。

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

leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/" rel="nofollow">1218. 最长定差子序列

分析：下面的代码在leetcode上会超时。

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

分析：用hash储存就不会超时了。

class Solution {
public:int longestSubsequence(vector<int>& arr, int difference) {unordered_map<int, int> hash;hash[arr[0]] = 1;int ret = 1;for (int i = 1; i < arr.size(); i++) {hash[arr[i]] = hash[arr[i] - difference] + 1;ret = max(ret, hash[arr[i]]);}return ret;}
};

leetcode.cn/problems/Q91FMA/" rel="nofollow">LCR 093. 最长的斐波那契子序列的长度

分析：同样地，如果不借助hash，时间复杂度会飙到$n^3$。

class Solution {
public:int lenLongestFibSubseq(vector<int>& arr) {int n = arr.size();if (n < 3) return 0;unordered_map<int, int> hash;vector<vector<int>> dp(n, vector<int>(n, 0));int ret = 0;hash[arr[0]] = 0;for (int i = 1; i < n; i++) {for (int j = i + 1; j < n; j++) {int a = arr[j] - arr[i];if(hash.count(a))dp[i][j] = dp[hash[a]][i] + 1;ret = max(ret, dp[i][j]);}hash[arr[i]] = i;}return ret == 0 ? 0 : ret + 2;}
};

leetcode.cn/problems/longest-arithmetic-subsequence/" rel="nofollow">1027. 最长等差数列

分析：本题与上一题没什么区别。

class Solution {
public:int longestArithSeqLength(vector<int>& nums) {int n = nums.size();vector<vector<int>> dp(n, vector<int>(n, 2));int ret = 2;unordered_map<int, int> hash;hash[nums[0]] = 0;for (int i = 1; i < n; i++) {for (int j = i + 1; j < n; j++) {int a = 2 * nums[i] - nums[j];if(hash.count(a))dp[i][j] = dp[hash[a]][i] + 1;ret = max(ret, dp[i][j]);}hash[nums[i]] = i;}return ret;}
};

leetcode.cn/problems/arithmetic-slices-ii-subsequence/" rel="nofollow">446. 等差数列划分 II - 子序列

分析：还是一样的套路，但是hash的封装应有所不同了。

class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {int n = nums.size();vector<vector<int>> dp(n, vector<int>(n));unordered_map<long long, vector<int>> hash;for (int i = 0; i < n; i++) hash[nums[i]].push_back(i);int sum = 0;for (int j = 2; j < n; j++) {for (int i = 1; i < j; i++) {long long k = (long long) 2 * nums[i] - nums[j];for (auto e : hash[k]) {if (e < i) dp[i][j] += dp[e][i] + 1;} sum += dp[i][j];}}return sum;}
};