LeetCode 3176.求出最长好子序列 I：动态规划（DP）

【LetMeFly】3176.求出最长好子序列 I：动态规划（DP）

力扣题目链接：https://leetcode.cn/problems/find-the-maximum-length-of-a-good-subsequence-i/

给你一个整数数组 nums 和一个 非负 整数 k 。如果一个整数序列 seq 满足在范围下标范围 [0, seq.length - 2] 中存在 不超过 k 个下标 i 满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为 好 序列。

请你返回 nums 中 好 子序列 的最长长度

 

示例 1：

输出：4

解释：

最长好子序列为 [1,2,1,1,3] 。

示例 2：

输出：2

解释：

最长好子序列为 [1,2,3,4,5,1] 。

 

提示：

• 1 <= nums.length <= 500
• 1 <= nums[i] <= 109
• 0 <= k <= min(nums.length, 25)

解题方法：动态规划

使用一个动态规划数组$dp$，其中$dp[i][l]$代表数组前$i$个元素的不超过$l$个相邻不同的好子序列的最大长度。

初始值$dp[i][0]=1$，其余值默认为$-1$就行，转移方程：

$$dp[i][l]=\min \{\begin{array}{ll}dp[i][l]& \\ dp[j][l]+1& \text{ if }nums[i]=nums[j]\\ dp[j][l-1]+1& \text{ if }nums[i]\ne nums[j]\text{ and }l>0\end{array}$$

三层循环，第一层用$i$从$0$到$len(nums)-1$，第二层用$l$从$0$到$k$，第三层用$j$从$0$到$i-1$。

• 时间复杂度$O(len(nums{)}^2\times k)$
• 空间复杂度$O(len(nums)\times k)$

更低复杂度请见下一题：求出最长好子序列 II

AC代码

C++

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

Python

from typing import Listclass Solution:def maximumLength(self, nums: List[int], k: int) -> int:dp = [[-1] * (k + 1) for _ in range(len(nums))]for i in range(len(nums)):dp[i][0] = 1for l in range(k + 1):for j in range(i):diff = int(nums[i] != nums[j])if l - diff >= 0:dp[i][l] = max(dp[i][l], dp[j][l - diff] + 1)return max(max(dp[i]) for i in range(len(nums)))

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/141992543