3176.求出最长好子序列I

链接：3176.求出最长好子序列I
难度：Medium
标签：数组、哈希表、动态规划
简介：请你返回删除所有数字字符以后剩下的字符串。

题解 1 - python

• 编辑时间：2024-09-06
• 执行用时：7064ms
• 内存消耗：16.84MB
• 编程语言：python
• 解法介绍：dp[i][k]表示以i下标为最后一个元素，在不超过k个约束的情况下的最大长度

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