摘要
Title: 3176. 求出最长好子序列 I
Categories: dp

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

3176. 求出最长好子序列 I

题意

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

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

思路

1. 设定三个状态，目前是哪个元素，前一个元素是什么，用了几次不相等的名额。然后就可以记忆化搜索了，但是空间占用很大
2. 设定两个状态，状态 dfs(i, h) 代表在数组 nums 中，当前到达第 i 个元素时，最多还能进行 h 次修改（即允许不同元素），可以得到的最长子序列长度。然后最后要求的是所有以i为结尾的最大值，状态量少很多

代码

class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class Std:
    pass

# ————————————————————— Division line ——————————————————————


class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:

        @lru_cache(None)
        def dfs(i: int, last: int, cnt: int):
            if i == len(nums):
                return 0

            ans = 0
            if nums[i] == last:
                ans = Math.max(ans, dfs(i + 1, nums[i], cnt) + 1)
            else:
                if cnt < k:
                    ans = Math.max(ans, dfs(i + 1, nums[i], cnt + 1) + 1)
                ans = Math.max(ans, dfs(i + 1, last, cnt))

            return ans

        ans = dfs(0, -1, -1)
        dfs.cache_clear()
        return ans

class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        
        @lru_cache(None)
        def dfs(i: int, h: int) -> int:
            if i == 0:
                return 1
            max_len = 1
            for j in range(i):
                if nums[i] == nums[j]:
                    max_len = Math.max(max_len, dfs(j, h) + 1)
                elif h > 0:
                    max_len = Math.max(max_len, dfs(j, h - 1) + 1)
            return max_len
        
        ans = 0
        n = len(nums)
        for i in range(n):
            ans = Math.max(ans, dfs(i, k))
        
        return ans