算法动态规划

最长好子序列1：猜想出最优子结构

字数统计: 791字   |   阅读时长: 3分
,

摘要: 猜出最优子结构并不容易

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，本文看一个动态规划的问题。依然是需要在草稿纸上推导小数据的情况时，猜出最优子结构。这是第一步难点，下一步是动态规划的优化，这一步也是难点。本文先解决对一个难点，下一篇文章我们看优化的问题。

题目

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

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

提示：

1
2
3
1 <= nums.length <= 500
1 <= nums[i] <= 1e9
0 <= k <= min(nums.length, 25)

示例 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] 。

题解

算法：动态规划

定义 $dp[i][k]$ 表示在前缀 $nums[0], \cdots, nums[i]$ 范围上，在选择 $nums[i]$ 的前提下，选出的子序列最多有 $k$ 个上坡或下坡，可选的最长子序列。

为了推导和实现方便，可以在 $nums$ 后面加一个其中没出现过的值，加入新值的 $nums$ 长度变为 $n+1$，新值位置为 $nums[n]$。

如果这样定义的话，答案为 $dp[n][k+1]$，也就是选择 $nums[n]$ 的前提下，选出的子序列最多 $k+1$ 个上坡或下坡（包含了 $nums[n]$ 本身），最长的长度，将其减 1 自然就是答案。

初始值出现在 $k=0$ 且 $i$ 左边没有与 $nums[i]$ 相等的元素的时候。此时 $dp[i][k] = 1$，即 $nums[i]$ 本身。

上述定义中 $i$ 为阶段，$k$ 为附加信息。推导过程按照 $i=0,1,\cdots,n$ 线性推导即可，在推导 $i$ 阶段的状态时，$i-1$ 阶段的状态已经推导完。状态转移方程如下：

其中 $f(j)$ 需要根据 $nums[j]$ 是否等于 $nums[i]$ 进行分类：

代码 (Python)

共有 $N$ 个阶段，每个阶段 $k$ 个状态，每次状态的推导还有 $O(N)$ 种决策，总时间复杂度为 $O(N^{2}k)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums.append(int(1e9+1))

        @lru_cache(int(1e8))
        def solve(i: int, k: int) -> int:
            if k == -1:
                return 0
            mx = 0
            for j in range(i):
                if nums[i] == nums[j]:
                    mx = max(mx, solve(j, k))
                else:
                    mx = max(mx, solve(j, k - 1))
            return 1 + mx

        return solve(n, k + 1) - 1
Share