What is the main pattern used to solve the "Maximum Total Reward Using Operations II" problem?

The problem primarily uses state transition dynamic programming to determine the best way to accumulate rewards by marking indices optimally.

How do I optimize my solution for the "Maximum Total Reward Using Operations II" problem?

Sorting the reward values array first is key to ensuring you always pick the largest rewards, followed by using dynamic programming to track state transitions for optimal reward accumulation.

What is the time complexity of the "Maximum Total Reward Using Operations II" problem?

The time complexity is dominated by the sorting step, which takes O(n log n), followed by the dynamic programming calculation that takes O(n).

What are common pitfalls when solving the "Maximum Total Reward Using Operations II" problem?

Common pitfalls include forgetting to sort the reward array, mishandling state transitions, and inefficiently managing dynamic programming states.

What is the optimal approach for solving the "Maximum Total Reward Using Operations II" problem?

The optimal approach involves sorting the reward array and then using dynamic programming to track and maximize the reward through optimal state transitions.

#3181

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

给你一个整数数组 rewardValues ，长度为 n ，代表奖励的值。最初，你的总奖励 x 为 0，所有下标都是未标记的。你可以执行以下操作任意次：从区间 [0, n - 1] 中选择一个未标记的下标 i 。如果 rewardValues[i] 大于你当前的总奖励 x ，则将…

数组动态规划位运算

题目描述

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

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

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

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

示例 1：

输入：rewardValues = [1,1,3,3]

输出：4

解释：

依次标记下标 0 和 2，总奖励为 4，这是可获得的最大值。

示例 2：

输入：rewardValues = [1,6,4,3,2]

输出：11

解释：

依次标记下标 0、2 和 1。总奖励为 11，这是可获得的最大值。

提示：

1 <= rewardValues.length <= 5 * 10⁴
1 <= rewardValues[i] <= 5 * 10⁴

lightbulb

解题思路

方法一：动态规划 + 位运算

我们定义 $f[i][j]$ 表示用前 $i$ 个奖励值，能否得到总奖励 $j$ 。初始时 $f[0][0] = \textit{True}$ ，其余值均为 $\textit{False}$ 。

我们考虑第 $i$ 个奖励值 $v$ ，如果我们不选择它，那么 $f[i][j] = f[i - 1][j]$ ；如果我们选择它，那么 $f[i][j] = f[i - 1][j - v]$ ，其中 $0 \leq j - v \lt v$ 。即状态转移方程为：

f[i][j] = f[i - 1][j] \vee f[i - 1][j - v]

最终答案为 $\max\{j \mid f[n][j] = \textit{True}\}$ 。

由于 $f[i][j]$ 只与 $f[i - 1][j]$ 和 $f[i - 1][j - v]$ 有关，我们可以优化掉第一维，只使用一个一维数组进行状态转移。另外，由于本题数据范围较大，我们需要使用位运算来优化状态转移的效率。

我们定义一个二进制数 $f$ 保存当前的状态，其中 $f$ 的第 $i$ 位为 $1$ 表示当前总奖励为 $i$ 是可达的。

观察上述状态转移方程 $f[j] = f[j] \vee f[j - v]$ ，这相当于取 $f$ 的低 $v$ 位，再左移 $v$ 位，然后与原来的 $f$ 进行或运算。

那么答案为 $f$ 的最高位的位置。

时间复杂度 $O(n \times M / w)$ ，空间复杂度 $O(n + M / w)$ 。其中 $n$ 是数组 rewardValues 的长度，而 $M$ 是数组 rewardValues 中的最大值的两倍。整数 $w = 32$ 或 $64$ 。

1

2

3

4

5

6

7

8

class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        nums = sorted(set(rewardValues))
        f = 1
        for v in nums:
            f |= (f & ((1 << v) - 1)) << v
        return f.bit_length() - 1

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Looks for an understanding of dynamic programming with state transitions.
question_mark
Evaluates ability to optimize solutions through sorting and state-based accumulation.
question_mark
Assesses proficiency in handling large arrays with efficient algorithms.

warning

常见陷阱

外企场景

error
Failing to sort the reward values first, which could lead to suboptimal choices during the selection of indices.
error
Not properly managing state transitions, resulting in incorrect calculations of the maximum reward.
error
Overcomplicating the problem by failing to leverage dynamic programming efficiently.

swap_horiz

进阶变体

外企场景

arrow_right_alt
A variant could involve adding constraints where only certain subsets of indices are allowed to be marked.
arrow_right_alt
Consider allowing a limited number of operations to be performed, requiring optimization of each move.
arrow_right_alt
Modify the problem to allow for non-integer reward values, changing the optimization dynamics.

help

常见问题

外企场景

继续练习

#3149 找出分数最低的排列 #3117 划分数组得到最小的值之和 #3276 选择矩阵中单元格的最大得分