Leetcode 3177. Find the Maximum Length of a Good Subsequence II
- Leetcode 3177. Find the Maximum Length of a Good Subsequence II
- 1. 解题思路
- 2. 代码实现
- 题目链接：3177. Find the Maximum Length of a Good Subsequence II
1. 解题思路
这一题我一开始的思路是直接使用暴力的动态规划的方式进行实现，结果遇到了内存爆炸的问题，后来看了一下别人的回答，整体的思路还是动态规划，但是存储结构上做了一些优化。
本质来说都是要做这么一个事：
if pre_num == nums[idx]:dp(idx, pre_num, k) = 1 + dp(idx+1, pre_num, k)
else:dp(idx, pre_num, k) = max(dp(idx+1, pre_num, k), 1 + dp(idx+1, nums[idx], k))
然后到具体实现上，如果直接这么实现无论是内存还是时间都扛不住，因此我们需要稍微做点优化，具体来说就是首先对pre_num进行一下cache，具体来说的话这里其实就是要分两种情况：
- 如果当前的数和前一个取值相同的情况
- 如果当前的数和前一个取值不同的情况
对于前者，我们不得不使用一个cache来存储所有可能的取值下的情况，对于后者，严格来说我们必须要找不同的情况，但是事实上我们可以偷个懒，直接取全部的情形，前者是后者的一个子集。
通过这种方式，就能够通过所有的测试样例……
2. 代码实现
给出python代码实现如下：
class Solution:def maximumLength(self, nums: List[int], k: int) -> int:n = len(nums)dp = [[0 for _ in range(k+1)] for _ in range(n)]same = [defaultdict(int) for _ in range(k+1)]diff = [0 for _ in range(k+1)]ans = 0for i, num in enumerate(nums):dp[i][0] = 1for j in range(k+1):dp[i][j] = 1 + same[j][num]if j > 0:dp[i][j] = max(dp[i][j], diff[j-1]+1)ans = max(ans, dp[i][j])for j in range(k+1):same[j][num] = max(same[j][num], dp[i][j])diff[j] = max(diff[j], dp[i][j])return ans
提交代码评测得到：耗时2052ms，占用内存29.4MB。