本文涉及知识点

C++动态规划
离散化

LeetCode3176. 求出最长好子序列 I

给你一个整数数组 nums 和一个 非负 整数 k 。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 中 最多只有 k 个下标 i 满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为 好 序列。
请你返回 nums 中 好 子序列 的最长长度。
示例 1：
输入：nums = [1,2,1,1,3], k = 2
输出：4
解释：
最长好子序列为 [1,2,1,1,3] 。
示例 2：
输入：nums = [1,2,3,4,5,1], k = 0
输出：2
解释：
最长好子序列为 [1,2,3,4,5,1] 。
提示：
1 <= nums.length <= 500
1 <= nums[i] <= 10⁹
0 <= k <= min(nums.length, 25)

容易想到的动态规划

dp[j][k] 表示以nums[j]结尾，k个不同下标的最长子序列列。空间复杂度：O(nk)
每个状态枚举前一个数字nums[i]，单个状态的时间复杂度：O(n)，总时间复杂度：O(nnk)。

动态规划

离散化

我们只关系值是否相等，不关系为多少。故将nums的最小值转成0，次小值转为1 $\cdots$

动态规划

dp1[i][j][k] 表示nums的前i个数字中，以j结尾，k个不同下标的最长子序列。
dp2[i][k] 表示nums的前i个数字中，任意数字结尾，k个不同下标的最长子序列。
用滚动向量：pre = dp[i] cur = dp[i+1]
用滚动向量后，空间复杂度：O(nk)

动态规划的填表顺序

枚举nums各值，枚举k。

动态规划的转移方程

dp1[i+1] = dp1[i] 不选择nums[i]
{ d p 1 [ i + 1 ] [ j ] [ k ] = d p 2 [ i ] [ k − 1 ] + 1 情况一，最后两元素不等 d p 1 [ i + 1 ] [ j ] [ k ] = d p 1 [ i ] [ j ] [ k ] 情况二，最后两元素相等 \begin{cases} dp1[i+1][j][k] = dp2[i][k-1]+1 && 情况一，最后两元素不等 \\ dp1[i+1][j][k] = dp1[i][j][k] && 情况二，最后两元素相等\\ \end{cases} {dp1[i+1][j][k]=dp2[i][k−1]+1dp1[i+1][j][k]=dp1[i][j][k]​​情况一，最后两元素不等情况二，最后两元素相等​
通过dp1更新dp2。
情况一改成任意两元素，也不会出错。如果是最后的两个元素相等，情况二会淘汰情况一。
单个状态的转移时间复杂度：O(1)，总时间复杂度：O(nk)

动态规划的初始值

dp1[0]和dp2[0]全为0，其它全为INT_MIN/2。

动态规划的返回值

dp2.back()的最大值。

错误代码

这个代码是O(nnk) ，因为cur1复制了n次。

class Solution {
		public:
			int maximumLength(vector<int>& nums, int K) {
				const int N = nums.size();
				unordered_map<int, int> mCode;
				for (auto& n : nums) {
					if (!mCode.count(n)) {
						mCode[n] = mCode.size();
					}
					n = mCode[n];
				}
				vector<vector<int>> pre1(N,vector<int>(K+1));
				vector<int> pre2(K + 1);
				for (int i = 0; i < N; i++) {
					auto cur1 = pre1;
					auto cur2 = pre2;
					auto& cur = cur1[nums[i]];
					for (int k = 0; k <= K; k++)
					{
						cur[k] = max(cur[k], pre1[nums[i]][k]+1);
						if( k > 0 ){ cur[k] = max(cur[k], pre2[k - 1] + 1); }						
						cur2[k] = max(cur2[k], cur[k]);
					}
					pre1.swap(cur1);
					pre2.swap(cur2);
				}
				return *max_element(pre2.begin(), pre2.end());
			}
		};

动态规划再次优化

动态规划的状态表示

dp1[j][k] 表示 值为j ，不同下标为k的最长序列。
dp[2] = 不同下标为k的最长系列。
用临时变量记录本次迭代的新值 auto cur = dp1[nums[i]];
计算完后，用cur更新dp1和dp2。
时间复杂度：O(nk)

代码

class Solution {
		public:
			int maximumLength(vector<int>& nums, int K) {
				const int N = nums.size();
				unordered_map<int, int> mCode;
				for (auto& n : nums) {
					if (!mCode.count(n)) {
						mCode[n] = mCode.size();
					}
					n = mCode[n];
				}
				vector<vector<int>> dp1(N,vector<int>(K+1));
				vector<int> dp2(K + 1);
				for (int i = 0; i < N; i++) {		
					auto cur = dp1[nums[i]];
					for (int k = 0; k <= K; k++)
					{
						cur[k] = max(cur[k], dp1[nums[i]][k]+1);
						if( k > 0 ){ cur[k] = max(cur[k], dp2[k - 1] + 1); }						
					}
					dp1[nums[i]] = cur;
					for (int k = 0; k <= K; k++)
					{
						dp2[k] = max(dp2[k], cur[k]);
					}
				}
				return *max_element(dp2.begin(), dp2.end());
			}
		};

单元测试

vector<int> nums;
		int k;
		TEST_METHOD(TestMethod11)
		{
			nums = { 1, 2, 1, 1, 3 }, k = 2;
			auto res = Solution().maximumLength(nums, k);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 1,2,3,4,5,1 }, k = 0;
			auto res = Solution().maximumLength(nums, k);
			AssertEx(2, res);
		}