Hard

题目描述

给你一个长度为 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 <= 5 * 10^4
  • 1 <= rewardValues[i] <= 5 * 10^4

提示：

  • 首先对奖励数组排序。
  • 如果我们决定应用一些奖励，按顺序应用它们总是最优的。
  • 状态转移为：如果 j - rewardValues[i] < rewardValues[i]，则 dp[i][j] = dp[i-1][j-rewardValues[i]]。
  • 注意 dp 数组是布尔数组。每个元素只需要 1 位，因此可以使用位集或类似的东西。

解题思路

这道题的核心思想是动态规划结合位操作优化。

基本思路：

  1. 首先对奖励数组排序，这样我们就能按从小到大的顺序处理奖励
  2. 使用动态规划，dp[i][j] 表示前 i 个奖励能否得到总和为 j 的状态
  3. 关键约束：只有当前总奖励 x < rewardValues[i] 时，才能选择该奖励

优化策略： 由于状态转移只涉及布尔值（能否达到某个和），我们可以用位操作来优化：

  • 使用 bitset 来表示所有可能的状态
  • 对于每个奖励 v，只考虑当前总和小于 v 的状态
  • 通过位移和位运算快速更新所有可达状态

状态转移：

  • 对于奖励 v，我们只关心总和在 [0, v-1] 范围内的状态
  • 如果状态 j 可达且 j < v，那么状态 j+v 也变为可达
  • 使用位操作：dp |= (dp & mask) « v，其中 mask 表示小于 v 的所有位

这种方法将时间复杂度从 O(nsum) 优化到 O(nsum/w)，其中 w 是机器字长。

代码实现

class Solution {
public:
    int maxTotalReward(vector<int>& rewardValues) {
        sort(rewardValues.begin(), rewardValues.end());
        rewardValues.erase(unique(rewardValues.begin(), rewardValues.end()), rewardValues.end());
        
        bitset<100001> dp;
        dp[0] = 1;
        
        for (int v : rewardValues) {
            bitset<100001> mask;
            for (int i = 0; i < v; i++) {
                mask[i] = 1;
            }
            dp |= (dp & mask) << v;
        }
        
        for (int i = 100000; i >= 0; i--) {
            if (dp[i]) return i;
        }
        return 0;
    }
};

class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        rewardValues = sorted(set(rewardValues))
        dp = 1  # 用整数的二进制位表示状态
        
        for v in rewardValues:
            mask = (1 << v) - 1  # 创建前v位都为1的掩码
            dp |= (dp & mask) << v
        
        # 找到最高位的1
        return dp.bit_length() - 1

public class Solution {
    public int MaxTotalReward(int[] rewardValues) {
        Array.Sort(rewardValues);
        var uniqueRewards = new HashSet<int>(rewardValues).ToArray();
        Array.Sort(uniqueRewards);
        
        var dp = new BitArray(100001);
        dp[0] = true;
        
        foreach (int v in uniqueRewards) {
            var newDp = new BitArray(dp);
            for (int j = 0; j < 100001 - v; j++) {
                if (dp[j] && j < v) {
                    newDp[j + v] = true;
                }
            }
            dp = newDp;
        }
        
        for (int i = 100000; i >= 0; i--) {
            if (dp[i]) return i;
        }
        return 0;
    }
}

var maxTotalReward = function(rewardValues) {
    rewardValues.sort((a, b) => a - b);
    const uniqueRewards = [...new Set(rewardValues)];
    
    let dp = new Set([0]);
    
    for (const v of uniqueRewards) {
        const newStates = new Set();
        for (const sum of dp) {
            if (sum < v) {
                newStates.add(sum + v);
            }
        }
        for (const state of newStates) {
            dp.add(state);
        }
    }
    
    return Math.max(...dp);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n * max_sum / w)其中 n 是数组长度，max_sum 是最大可能和，w 是机器字长
空间复杂度O(max_sum)存储所有可能状态的位集