3181. 执行操作可获得的最大总奖励 II

#python #leetcode #dp #bit-manipulation

题目描述

关联：

• https://leetcode.cn/problems/maximum-total-reward-using-operations-ii/description/
• https://leetcode.cn/problems/maximum-total-reward-using-operations-i/description/ （3180）

题目描述

给你一个整数数组 rewardValues，长度为 n，代表奖励的值。

最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次：

• 从区间 [0, n - 1] 中选择一个 未标记 的下标 i。
• 如果 rewardValues[i] 大于 你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并 标记 下标 i。

以整数形式返回执行最优操作能够获得的 最大 总奖励。

本题和 3180. 执行操作可获得的最大总奖励 I 的区别在于，本题的输入范围更大。

\(1 \leq \text{len}(rewardValues) \leq 5 \times 10^4\)

\(1 \leq rewardValues[i] \leq 5 \times 10^4\)

解题思路

如果继续沿用 3180. 执行操作可获得的最大总奖励 I 的解法，会发现在输入范围更大的情况下，动态规划的空间复杂度会变得非常高，会超出内存限制。

3180 的动态规划解法

class Solution:
    def maxTotalReward(self, rewardValues: list[int]) -> int:
        rewardValues = sorted(set(rewardValues))
        n = len(rewardValues)
        m = max(rewardValues) * 2 - 1

        dp = [[0] * (m + 1) for _ in range(n + 1)]
        dp[0][0] = 1

        for i in range(1, n + 1):
            for j in range(2 * rewardValues[i - 1] - 1, -1, -1):
                dp[i][j] = dp[i - 1][j]
                if j >= rewardValues[i - 1]:
                    dp[i][j] |= dp[i - 1][j - rewardValues[i - 1]]

        return max(j for j in range(m + 1) if dp[-1][j])

这个解法的时间复杂度和空间复杂度均为 \(O(n \cdot m)\)，因此无论如何都会出现超时和超出内存限制的情况。

注意到我们的二维数组 dp 只保存 0 或者 1，因此我们可以将 j 所在的维度变成二进制数，配合位运算，从而将二维数组压缩成一维数组。

另一方面，抛开这个题目不谈，关于动态规划的题目，一般都是可以通过某些方式来降低一个维度的。例如 0-1 背包问题，我们可以通过逆序遍历来降低一个维度。本题中的 i 维度也可以完全消去，我们稍后再分析原因。

现在我们可以仅通过一个整数 mask 来代替 dp 二维数组。

以测试用例 [1, 6, 4, 3, 2] 为例：

\(m = 6 \times 2 - 1 = 11\)

	0	1	2	3	4	5	6	7	8	9	10	11
0	1	0	0	0	0	0	0	0	0	0	0	0
1	1	1	0	0	0	0	0	0	0	0	0	0
2	1	1	1	1	0	0	0	0	0	0	0	0
3	1	1	1	1	1	1	0	0	0	0	0	0
4	1	1	1	1	1	1	1	1	0	0	0	0
5	1	1	1	1	1	1	1	1	1	1	1	1

首先需要把：

dp = [[0] * (m + 1) for _ in range(n + 1)]
dp[0][0] = 1

改成：

mask = 1  # 相当于 dp[0][0] = 1

接下来需要进行 n 轮遍历。注意到 for i in range(1, n + 1) 中的 i 仅在 rewardValues[i - 1]、dp[i - 1] 和 dp[i] 中出现。而 rewardValues[i - 1] 只是单纯对 rewardValues 的遍历。

因此可以将：

for i in range(1, n + 1):
    # rewardValues[i - 1] 相关操作

改成：

for reward in rewardValues:
    # reward 相关操作

现在考虑

for j in range(2 * reward - 1, -1, -1):
    dp[i][j] = dp[i - 1][j]  # 只是复制上一行的值
    if j >= reward:
        dp[i][j] |= dp[i - 1][j - reward]

j >= reward 这一行要求我们只处理 reward 右边那些列的值，而左边的值从上一行复制，由于奖励都可以拿到，因此全部为 1。

这一操作相当于 mask 的低 reward 位全为 1，高位全为 0。用位运算表示的话，就是 mask & (1 << reward) - 1。

dp[i][j] |= dp[i - 1][j - reward] 这一行要求我们将 reward 右边的值与上一行的值进行或运算，而左边的值不变。我们可以将这个掩码左移 reward 位，模拟添加 reward 到每个状态。

所以我们最终的状态转移可以改为：

mask |= (mask & (1 << reward) - 1) << reward

最后我们需要返回的是 mask 中最大的 j，即 mask 中最高位的 1 的位置。Python 中已经有 bit_length 函数可以直接返回这个值，但是需要记得减去 1，因为我们的列是从 0 开始的。

return mask.bit_length() - 1

完整题解

class Solution:
    def maxTotalReward(self, rewardValues: list[int]) -> int:
        rewardValues = sorted(set(rewardValues))
        mask = 1

        for reward in rewardValues:
            mask |= (mask & (1 << reward) - 1) << reward

        return mask.bit_length() - 1

复杂度分析

• 时间复杂度：\(O(n)\)，其中 n 是 rewardValues 的长度。
• 空间复杂度：\(O(1)\)，虽然这个整数可能很大（1 << 50000），但是由于是常数级别的空间，因此他的空间复杂度确实是 \(O(1)\)。

评论