3176. 求出最长好子序列 I Python-Leetcode

📕题干

中等

给你一个整数数组 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)

📖题解

谬论

💻代码

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        l = 1
        for i in range(2**len(nums)):
            result = []
            n = 0
            a = bin(i)[2:]
            if len(a) < len(nums):
                a = '0'*(len(nums)-len(a)) + a
            for m,j in enumerate(a):
                if j == '0':
                    result += [nums[m]]
            for index in range(len(result)-1):
                if result[index] != result[index+1]:
                    n += 1
            if n <= k and len(result) > l:
                l = len(result)
        return l

执行用时：NaN 消耗内存：NaN

🤔思路

直接暴力求解，用二进制表示去与舍，计算全部子集。

❗ 后果

时间复杂度达到了_O(2N×N)_，荒谬至极。

正解

💻代码

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [[1]*(k+1) for _ in range(n)]
        for i in range (1,n):
            for j in range(k+1):
                for m in range(i):
                    if nums[m] == nums[i]:
                        dp[i][j] = max(dp[i][j],dp[m][j]+1)
                    elif j > 0:
                        dp[i][j] = max(dp[i][j],dp[m][j-1]+1)
        return max(max(a) for a in dp)

执行用时：6357ms 消耗内存：16.78MB

🤔思路

此题考虑动态规划，构建一个二维数组dp，用dp[i][j]表示以nums[i]结尾的含有j个不同数字的子序列的最长长度。

先对dp进行初始化，无论j为多少，dp[i][j]始终大于等于1，可以初始化dp中所有元素为1。然后对dp中的元素依次遍历，由于考虑的是以nums[i]结尾的子序列，也就是说遍历到的nums[i]必须取，所以只需要遍历i之前的元素。若nums[i] == nums[m]，此时的dp[i][j]可以表示为dp[m][j]+1，然后取最大值。若nums[i] != nums[m]，也就意味着j要增加1，此时的dp[i][j]可以表示为dp[m][j-1]+1，然后取最大值。

最终得到dp的最大值，返回。

时间复杂度 $O(N^2\*k)$

😅吐槽

对于新手我来说，这真的算不上中等，太困难了，做了一下午，光动态规划就理解了半天。