算法动态规划

最长好子序列2：动态规划难题的完整思考过程

字数统计: 2.3k字   |   阅读时长: 9分
, ,

摘要: 避免枚举所有可能的决策

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

各位好，本文是上一篇文章 最长好子序列1：猜想出最优子结构 的延续，题目完全相同，只是数据量级增加了，原有的算法必须优化。

大的思想比较好理解，就是在推导 $n$ 个阶段的过程中，每步状态转移有 $O(n)$ 种可能的决策需要考虑，有没有办法使得在状态转移时，通过历史阶段的信息排除掉大量无效的决策，使得不用枚举所有的决策。

思想虽然直接，但是设计出算法并不容易，我们在分析的过程中发现原有的状态表示无法避免枚举所有决策，需要对状态表示进行修改，这又是需要大胆猜想的地方。

本文写的比较冗长，尽可能保留了思考过程，而不是直接给出最终算法。方便读者阅读出对于动态规划的难题，从结合样例的分析猜想出最优子结构，到为了避免枚举素有决策而修改状态表示，在新的状态表示下避免枚举所有决策的完整过程。

题目

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

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

提示：

1
2
3
1 <= nums.length <= 5e3
1 <= nums[i] <= 1e9
0 <= k <= min(nums.length, 50)

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

动态规划：猜出最优子结构

回顾动态规划的建立过程。以下内容同上一篇文章 。

定义 $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]$ 进行分类：

转移方程分析

下面观察状态转移方程进行优化。

在考虑 $dp[i][k]$ 的状态转移时，我们需要查询的是 $0 \leq j < i$ 时 $dp[j][k]$ 和 $dp[j][k-1]$ 的最大值。

记 $x = nums[i]$，也就是在 $0\leq j < i$ 范围内要查询：

  • 如果 $nums[0],\cdots,nums[i-1]$ 中有元素等于 $x$，那么 $dp[j][k]$ 的最大值是多少，要求 $nums[i] = nums[j]$。
  • 如果 $nums[0],\cdots,nums[i-1]$ 中有元素不为 $x$，那么 $dp[j][k-1]$ 的最大值是多少。要求 $nums[i] \neq nums[j]$

一个自然的想法就是在推导阶段 $i$ 的过程中保存历史阶段中最大的 $dp[j][k]$ 和 $dp[j][k-1]$。

在以上需求中，前半段比较简单，可以建立一个哈希表保存 $nums[0],\cdots,nums[i-1]$ 的元素即可判断历史阶段有没有 $x$。

但后半段有个严重的问题，以第一条查询为例，历史阶段有 $x$，即要使用 $dp[j][k]$ 的最大值，但最大值点 $j$ 对应的值是否为 $x$ 是需要判断的。

也就是说，在推导的过程中，历史阶段的 $dp[j][k]$、$dp[j][k-1]$ 的最大值是保存了，但是为了判断 $nums[j] = nums[i]$ 还是无法避免枚举 $j$。

修改状态表示

还是考虑线性地推导 $i$ 的过程，记 $x = nums[i]$，我们要求的是以 $x = nums[i]$ 结尾的，最多有 $k$ 个相邻不同的子序列的最长长度。

由于转移的过程中我们要判断 $x$ 值，因此可以弱化 $i$ 而强调 $x$，DP 状态的表示可以这样设计：

定义 $dp[x][k]$ 表示以 $x$ 结尾，最多有 $k$ 个相邻不同的子序列的最长长度。这里阶段依然是 $i$，状态表示中的 $x, k$ 均为附加信息。

这样定义的话，答案为当 $i$ 推导完之后的 $\max\limits_{x}dp[x][k]$。下面考虑状态转移方程：

以 $x$ 结尾，一种简单情况是 $x$ 本身，即长为 1 的子序列，如果长度大于 1，则考虑 $nums[0],\cdots,nums[i-1]$ 范围的子序列：

  • 情况1：该子序列以 $x$ 结尾，那么我们需要知道 $0\leq j < i$ 范围内，以 $x$ 结尾的子序列最长长度是多少，由于 $i$ 是线性推导的，这个值就存在 $dp[x][k]$ 中，因此仅需将 $dp[x][k]$ 自增 1 即可。
  • 情况2：该子序列不以 $x$ 结尾，不妨记结尾为 $y$，那么我们要知道的是 $0\leq j < i$ 范围内，所有的不等于 $x$ 的 $y$ 值中 $dp[y][k-1]$ 的最大值。

在情况2 中，如果枚举所有的 $y$ 来得到 $\max\limits_{y}dp[y][k-1]$，又成了 $O(n)$ 的枚举。下面我们要解决的是如何不枚举 $y$ 而得到 $dp[y][k-1]$ 的最大值。

优化：减少无效决策

当 $k$ 固定的时候，假如我们记 $mx_{1}$ 表示 $0\leq j < i$ 范围的元素 $y$ 中，$dp[y][k-1]$ 的最大值，记其为 $mx_{1} = dp[y_1][k-1]$，如果 $y_1 \neq x$，则 $mx_{1}$ 可以直接用，问题在于 $x = y_1$ 的处理。

由于 $dp$ 状态表示中 $x$ 就是值本身，因此 $dp[y][k - 1]$ 最大值当 $y=y_{1}$ 取到的最大值 $dp[y_{1}][k-1]$ 如果因为 $x = y_1$ 而无法用，那么次大值 $mx_{2} = dp[y_2][k-1]$ 就肯定不会出现 $y_2 = x$ 的情况，那么次大值 $mx_{2}$ 就可以直接用。

这里体现了以下标 $i$ 作为状态表示和以值 $x$ 作为状态表示的区别，如果是以下标 $i$ 作为状态表示，当 $nums[j_{1}] = x$ 时，维护的最大值 $mx_{1} = dp[j_{1}][k-1]$ 不能直接用，则次大值 $mx_{2} = dp[j_{2}][k-1]$ 也可能出现 $nums[j_{2}] = x$ 的情况，那就难免需要枚举 $j$ 了。

最终算法

定义 $dp[k][x]$ 表示以 $x$ 结尾，最多有 $k$ 个相邻不同的子序列的最长长度。这里阶段依然是 $i$，状态表示中的 $x, k$ 均为附加信息。

依次枚举 $i=0,1,\cdots,n-1$，当枚举到 $i$ 时，记 $x = nums[i]$。

然后再依次枚举 $k=0,1,…,K$，如果 $dp[k]$ 下没有 $x$，则新增 $x$，将其值设置为 1；如果 $dp[k]$ 下有 $x$ 则将 $dp[k][x]$ 自增 1。

在枚举的过程中，维护 $dp[k-1][y]$ 的最大值 $(y_{1}, mx_{1}[k - 1])$ 和次大值 $(y_{2}, mx_{2}[k - 1])$。那么此时若 $y_{1} = x$ 则用 $mx_{2}[k - 1]$ 更新 $dp[k][x]$，即 dp[k][x] = max(dp[k][x], mx2[k - 1] + 1)；若 $y_{1} \neq x$，则用 $mx_{1}[k - 1]$ 更新 $dp[k][x]$，即 dp[k][x] = max(dp[k][x], mx1[k - 1] + 1)。

更新完 $dp[k][x]$ 后，属于阶段 $i$ 的状态 $dp[k][x]$ 就推导完了。此时用 $(x, dp[k][x])$ 更新 $mx_{1}[k]$ 和 $mx_{2}[k]$，然后进行下一个状态的推导即可。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def maximumLength(self, nums: List[int], K: int) -> int:
        dp = [{} for _ in range(K + 1)]
        n = len(nums)
        mx1 = [(-1, 0) for _ in range(K + 1)]
        mx2 = [(-1, 0) for _ in range(K + 1)]
        for i in range(n):
            x = nums[i]
            for k in range(K + 1):
                if x not in dp[k]:
                    dp[k][x] = 1
                else:
                    dp[k][x] += 1
                if k > 0:
                    if mx1[k - 1][0] == x:
                        dp[k][x] = max(dp[k][x], mx2[k - 1][1] + 1)
                    else:
                        dp[k][x] = max(dp[k][x], mx1[k - 1][1] + 1)
                if dp[k][x] > mx1[k][1]:
                    mx2[k] = mx1[k]
                    mx1[k] = (x, dp[k][x])
                elif dp[k][x] > mx2[k][1]:
                    mx2[k] = (x, dp[k][x])
        ans = 0
        for x in dp[K]:
            ans = max(ans, dp[K][x])
        return ans
Share