算法动态规划

DP优化思路：用变量记录已推导状态的最值，供后续状态的推导使用

字数统计: 1.3k字   |   阅读时长: 5分
, ,

摘要: 一个动态规划优化的直接思路

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

在某些动态规划的问题中，状态转移方程类似于以下形式：

也就是我们需要此前阶段已经算过的状态中的最值，根据具体问题，范围可能不是 $0\leq i < j$ 这么简单，还会有别的条件。

对于一些简单问题，直接用变量记录推导状态所需的最值即可。这样如果状态转移方程中函数 $f$ 的计算是 $O(1)$，则状态转移即可在 $O(1)$ 完成，本文我们看一个相关的问题。

题目

给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。

你 一开始 在数组的位置 0 处，你可以按照下述规则访问数组中的其他位置：

  • 如果你当前在位置 i ，那么你可以移动到满足 i < j 的 任意 位置 j 。
  • 对于你访问的位置 i ，你可以获得分数 nums[i] 。
  • 如果你从位置 i 移动到位置 j 且 nums[i] 和 nums[j] 的 奇偶性 不同，那么你将失去分数 x 。

请你返回你能得到的 最大 得分之和。

注意 ，你一开始的分数为 nums[0] 。

提示：

1
2
2 <= nums.length <= 1e5
1 <= nums[i], x <= 1e6

示例 1：
输入：nums = [2,3,6,1,9,2], x = 5
输出：13
解释：我们可以按顺序访问数组中的位置：0 -> 2 -> 3 -> 4 。
对应位置的值为 2 ，6 ，1 和 9 。因为 6 和 1 的奇偶性不同，所以下标从 2 -> 3 让你失去 x = 5 分。
总得分为：2 + 6 + 1 + 9 - 5 = 13 。

示例 2：
输入：nums = [2,4,6,8], x = 3
输出：20
解释：数组中的所有元素奇偶性都一样，所以我们可以将每个元素都访问一次，而且不会失去任何分数。
总得分为：2 + 4 + 6 + 8 = 20 。

题解

算法：动态规划

问题是从 $nums[0]$ 起始，可以取得的最大分数和。

初始位置 $nums[0]$ 必须要选，然后考虑下一步的选择，$nums[1], nums[2], \cdots, nums[n-1]$ 都有可能。假设选择了 $nums[1]$，就要考虑从 $nums[1]$ 起始，可以取到的最大分数和。这里就有了最优子结构的雏形。

定义 $dp[j]$ 表示 $nums[0], \cdots, nums[j]$ 这段前缀上，以 $nums[j]$ 作为终点可以取得的最大分数和。这样定义的话，答案就是 $\max\limits_{0\leq i < n}dp[i]$。状态转移方程如下：

一共有 $n$ 个状态，在每个状态上需要 $O(n)$ 进行转移，因此总时间复杂度为 $O(n^{2})$。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]
        for j in range(1, n):
            mx = 0
            for i in range(j):
                if nums[i] % 2 == nums[j] % 2:
                    mx = max(mx, dp[i])
                else:
                    mx = max(mx, dp[i] - x)
            dp[j] = nums[j] + mx

        return max(dp)

优化：记录已推导状态的最值

在推导 $dp[j]$ 时，刚刚是枚举 $0\leq i < j$，根据 $nums[i]$ 与 $nums[j]$ 的奇偶性关系，寻找 $dp[i]$ 或 $dp[i] - x$ 的最大值。

一个很自然的想法是，在推导完成 $dp[i]$ 后，能不能将一些后续需要的信息记录下来，使得推导后续状态 $dp[j]$ 时，参考这些信息即可立即知道我们所需的最值，而不用再枚举 $0\leq i < j$ 了。

由于涉及到奇偶性，在推导完成 $dp[i]$ 之后，我们可以记录下面几个信息：

  • 在前缀 $nums[0],\cdots,nums[i]$ 上，以奇数结尾的 $dp$ 的最大值，记其为 $mx_{odd}$；
  • 在前缀 $nums[0],\cdots,nums[i]$ 上，以偶数结尾的 $dp$ 的最大值，记其为 $mx_{even}$。

这样 $dp[j]$ 的状态转移方程就可以简化如下：

如果 $nums[j]$ 为奇数，则为：

如果 $nums[j]$ 为偶数，则为：

还是 $n$ 个状态，但是状态转移时不需要 $O(n)$ 枚举了，因此总时间复杂度变为 $O(n)$。

这里需要注意由于有 $-x$ 的存在，$dp$ 是可能存在负数的，因此初始化的时候，应该将 $dp$ 以及 $mx_{odd}, mx_{even}$ 都设为 -INF。

代码 (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
28
29
INF = int(1e9)

class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        n = len(nums)
        dp = [-INF / 2] * n
        dp[0] = nums[0]
        mx_odd = -INF
        mx_even = -INF
        if nums[0] % 2 == 1:
            mx_odd = dp[0]
        else:
            mx_even = dp[0]

        for j in range(1, n):
            if nums[j] % 2 == 1:
                if mx_odd != -INF:
                    dp[j] = max(dp[j], nums[j] + mx_odd)
                if mx_even != -INF:
                    dp[j] = max(dp[j], nums[j] + mx_even - x)
                mx_odd = max(mx_odd, dp[j])
            else:
                if mx_odd != -INF:
                    dp[j] = max(dp[j], nums[j] + mx_odd - x)
                if mx_even != -INF:
                    dp[j] = max(dp[j], nums[j] + mx_even)
                mx_even = max(mx_even, dp[j])

        return max(dp)
Share