目标
给你一个整数数组 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] 。示例 2：
输入：nums = [1,2,3,4,5,1], k = 0
输出：2
解释：
最长好子序列为 [1,1] 。说明：
- 1 <= nums.length <= 500
- 1 <= nums[i] <= 10^9
- 0 <= k <= min(nums.length, 25)
提示：
- The absolute values in nums don’t really matter. So we can remap the set of values to the range [0, n - 1].
- Let
dp[i][j]be the length of the longest subsequence till index j with at most i positions such that seq[i] != seq[i + 1]. - For each value x from left to right, update
dp[i][x] = max(dp[i][x] + 1, dp[i - 1][y] + 1), where y != x.
思路
求整数数组 nums 的子序列，要求子序列中最多存在 k 个下标 i 满足 seq[i] != seq[i + 1]，即至多 k 对相邻元素 不同。
只要选出了子序列，那么相邻元素 不同 的对数就已经确定。
记忆化搜索超时了 // todo
代码