What is the main pattern used in Maximum Total Reward Using Operations I?

The problem primarily relies on state transition dynamic programming, tracking rewards accumulated as indices are marked.

Should I sort rewardValues before applying dynamic programming?

Sorting can simplify state transitions and ensure higher rewards are considered in an optimal sequence.

What is the time complexity of the DP solution?

A naive implementation is O(n^2) due to nested state transitions, but optimizations can reduce it depending on the DP update strategy.

How do I avoid double-counting rewards in this problem?

Carefully define DP states to track whether an index is already marked and only update states that represent valid sequences.

Can this DP approach handle large arrays efficiently?

Yes, with proper state management and possible optimizations like prefix sums or reduced state representation, it scales to arrays of length up to 2000.

#3180

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

给你一个整数数组 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 <= 2000
1 <= rewardValues[i] <= 2000

lightbulb

解题思路

方法一：排序 + 记忆化搜索 + 二分查找

我们可以对奖励值数组 rewardValues 进行排序，然后使用记忆化搜索的方法求解最大总奖励。

我们定义一个函数 $\textit{dfs}(x)$ ，表示当前总奖励为 $x$ 时，能够获得的最大总奖励。那么答案为 $\textit{dfs}(0)$ 。

函数 $\textit{dfs}(x)$ 的执行过程如下：

二分查找数组 rewardValues 中第一个大于 $x$ 的元素的下标 $i$ ；
遍历数组 rewardValues 中从下标 $i$ 开始的元素，对于每个元素 $v$ ，计算 $v + \textit{dfs}(x + v)$ 的最大值。
将结果返回。

为了避免重复计算，我们使用记忆化数组 f 记录已经计算过的结果。

时间复杂度 $O(n \times (\log n + M))$ ，空间复杂度 $O(M)$ 。其中 $n$ 是数组 rewardValues 的长度，而 $M$ 是数组 rewardValues 中的最大值的两倍。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        @cache
        def dfs(x: int) -> int:
            i = bisect_right(rewardValues, x)
            ans = 0
            for v in rewardValues[i:]:
                ans = max(ans, v + dfs(x + v))
            return ans

        rewardValues.sort()
        return dfs(0)

speed

复杂度分析

指标	值
时间	complexity depends on how the state transitions are computed, typically O(n^2) in naive DP or O(n log n) with optimizations. Space complexity depends on the DP table size, usually O(n) for a 1D table, reflecting the reward states at each index.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Watch for proper DP initialization and edge cases when indices are at the array boundaries.
question_mark
Prioritize understanding how each operation affects subsequent states to avoid overcounting rewards.
question_mark
Explain your reasoning for sorting or not sorting the array as it directly impacts transition correctness.

warning

常见陷阱

外企场景

error
Ignoring the effect of previous operations on future state transitions, leading to suboptimal total rewards.
error
Incorrectly updating DP states, which can either double-count rewards or miss valid sequences.
error
Not handling edge indices properly, which can cause array out-of-bounds errors or wrong maximum computation.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Limit the number of operations allowed and compute maximum reward under operation constraints.
arrow_right_alt
Include negative reward values to test state transition handling with mixed contributions.
arrow_right_alt
Extend to multi-dimensional reward arrays, requiring more complex DP state tracking.

help

常见问题

外企场景

继续练习

#3181 执行操作可获得的最大总奖励 II #3177 求出最长好子序列 II #3176 求出最长好子序列 I