3176.求出最长好子序列 I

【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：

输入：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] <= 109
• 0 <= k <= min(nums.length, 25)

解题方法：动态规划

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

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

$$dp[i][l] = \min \begin{cases}
dp[i][l] & \
dp[j][l] + 1 & \text{ if } nums[i]=nums[j]\
dp[j][l - 1] + 1 & \text{ if } nums[i] \neq nums[j] \text{ and } l \gt 0
\end{cases}$$

三层循环，第一层用$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 List

class 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] = 1
            for 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