Medium

题目描述

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

最初，你的总奖励 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

解题思路

这是一个动态规划问题。关键观察是：如果我们决定选择某些奖励，那么按照奖励值从小到大的顺序选择总是最优的。

解题思路

  1. 排序预处理：首先对奖励数组进行排序。这样可以确保我们在考虑奖励时，较小的奖励先被考虑。

  2. 状态定义：定义 dp[i][j] 表示考虑前 i 个奖励时，是否能够获得恰好 j 点的总奖励。

  3. 状态转移：对于第 i 个奖励 rewardValues[i]，我们有两种选择：

    • 不选择：dp[i][j] = dp[i-1][j]
    • 选择：当 j - rewardValues[i] < rewardValues[i] 时（即当前总奖励小于这个奖励值），可以从状态 j - rewardValues[i] 转移而来

  4. 优化空间：由于状态转移只依赖前一层，可以使用一维数组优化空间。

  5. 寻找答案：遍历所有可能的总奖励值，找到最大的可达到的值。

核心思想是贪心 + DP：排序保证了贪心策略的正确性，而DP确保我们能找到所有可能的状态组合。

代码实现

class Solution {
public:
    int maxTotalReward(vector<int>& rewardValues) {
        sort(rewardValues.begin(), rewardValues.end());
        
        int maxVal = rewardValues.back();
        vector<bool> dp(2 * maxVal, false);
        dp[0] = true;
        
        for (int reward : rewardValues) {
            for (int j = reward - 1; j >= 0; j--) {
                if (dp[j]) {
                    dp[j + reward] = true;
                }
            }
        }
        
        for (int i = 2 * maxVal - 1; i >= 0; i--) {
            if (dp[i]) {
                return i;
            }
        }
        
        return 0;
    }
};

class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        rewardValues.sort()
        
        max_val = rewardValues[-1]
        dp = [False] * (2 * max_val)
        dp[0] = True
        
        for reward in rewardValues:
            for j in range(reward - 1, -1, -1):
                if dp[j]:
                    dp[j + reward] = True
        
        for i in range(2 * max_val - 1, -1, -1):
            if dp[i]:
                return i
        
        return 0

public class Solution {
    public int MaxTotalReward(int[] rewardValues) {
        Array.Sort(rewardValues);
        
        int maxVal = rewardValues[rewardValues.Length - 1];
        bool[] dp = new bool[2 * maxVal];
        dp[0] = true;
        
        foreach (int reward in rewardValues) {
            for (int j = reward - 1; j >= 0; j--) {
                if (dp[j]) {
                    dp[j + reward] = true;
                }
            }
        }
        
        for (int i = 2 * maxVal - 1; i >= 0; i--) {
            if (dp[i]) {
                return i;
            }
        }
        
        return 0;
    }
}

var maxTotalReward = function(rewardValues) {
    rewardValues.sort((a, b) => a - b);
    
    const maxVal = rewardValues[rewardValues.length - 1];
    const dp = new Array(2 * maxVal).fill(false);
    dp[0] = true;
    
    for (const reward of rewardValues) {
        for (let j = reward - 1; j >= 0; j--) {
            if (dp[j]) {
                dp[j + reward] = true;
            }
        }
    }
    
    for (let i = 2 * maxVal - 1; i >= 0; i--) {
        if (dp[i]) {
            return i;
        }
    }
    
    return 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n × m)其中 n 是数组长度，m 是最大奖励值，需要遍历所有奖励和所有可能的状态
空间复杂度O(m)需要 O(2×maxVal) 的 dp 数组来存储状态