3180. 执行操作可获得的最大总奖励 I

#python #leetcode #dp

题目描述¶

关联：https://leetcode.cn/problems/maximum-total-reward-using-operations-i/description/

本题的考点是动态规划。

题目描述

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

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

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

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

这道题的输入范围设置得很小：

\(1 \leq \text{len}(rewardValues) \leq 2000\)

\(1 \leq rewardValues[i] \leq 2000\)

解题思路¶

这个题看起来是用贪心算法，即先按从小到大排序，再依次加入到总奖励中。

但是贪心算法是错误的，请看这个示例：

[1, 6, 4, 3, 2]

它排序后是 [1, 2, 3, 4, 6]，如果按照贪心算法，那么选取的元素分别是：

选取 1，总奖励 1
2 > 1，选取 2，总奖励 3
3 == 3，跳过
4 > 3，选取 4，总奖励 7
6 < 7，跳过

由此总奖励是 7，但是实际上应该这么取：

选取 1，总奖励 1
选取 4，总奖励 5
选取 6，总奖励 11

显然贪心算法在这里不能求出全局最优解，看来必须使用动态规划（无需考虑递归，这种题递归必超时）。

说到动态规划就不得不提到我们学过的 0-1 背包问题：

0-1 背包问题

有 n 个物品，每个物品的重量为 weight[i]，价值为 value[i]，背包的容量为 C，求在不超过背包容量的情况下，如何使得背包中的物品价值最大。

解决 0-1 背包问题的状态转移方程的关键就在于一个物品该不该选，而这个题目也是一样的。

我们使用一个二维数组 dp 来记录状态，dp[i][j] 表示在考虑前 i 个奖励时，总价值为 j 的情况是否能够达到。

这个数组的 j 的最大值只会达到 max(rewardValues) * 2 - 1 而不是 sum(rewardValues)，因为在执行最后一次选取时，先前已选奖励的总价值不会超过 max(rewardValues)。

对于一个奖励 rewardValues[i]，我们有两种选择：

不选取这个奖励，那么 dp[i][j] = dp[i - 1][j]
选取这个奖励，那么 dp[i][j] |= dp[i - 1][j - rewardValues[i]]

最后需要返回的是在考虑所有奖励的情况下，最大的奖励值。

值得注意的是，题目里并没有说每个奖励各不相同，但是你根本不可能选取同样的奖励两次，因此我们必须先去重才能确定 i 的范围。否则在动态规划中可能会直接导致计算错误。

完整题解¶

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)\)，其中 n 是 rewardValues 的长度，m 是 rewardValues 的最大值。

空间复杂度：\(O(n \cdot m)\)。