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

【LetMeFly】3180.执行操作可获得的最大总奖励 I：动态规划

力扣题目链接：https://leetcode.cn/problems/maximum-total-reward-using-operations-i/

给你一个整数数组 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

解题方法：动态规划

使用一个布尔类型的数组$dp$，其中$dp[i]$代表总奖励$i$是否有办法达到。初始值除了$dp[0]$为$true$外其余值全部为$false$。假设$rewardValues$中的最大元素为$M$，则总奖励一定不会超过$M - 1 + M$，因此数组大小为$2 * M$。

不失一般性，我们先对给定数组排个序。遍历数值中的每个元素，假设当前元素为$x$，那么$[0, x - 1]$范围内的任意一个“奖励都能加上$x$”。也就是说，如果$dp[i]$为$true$，那么$dp[i + x]$也将为$true$，其中$0\leq i\leq x - 1$。

因此有状态转移方程$dp[i + x] |= dp[i]$，其中$0\leq i\leq x - 1$。

• 时间复杂度$O(n\log n + nm)$，其中$n=len(rewardValues), m = \max(rewardValues)$
• 空间复杂度$O(\log n + m)$

时空复杂度上如果想除以一个系统位数，可以考虑【LetMeFly】3181.执行操作可获得的最大总奖励 II：动态规划+位运算优化的位运算优化

AC代码

C++

class Solution {
public:
    int maxTotalReward(vector<int>& rewardValues) {
        sort(rewardValues.begin(), rewardValues.end());
        vector<bool> dp(rewardValues.back() * 2);
        dp[0] = true;
        for (int t : rewardValues) {  // [t + 0, t + t - 1]
            for (int x = t * 2 - 1; x >= t; x--) {
                dp[x] = dp[x] | dp[x - t];  // dp[x] |= dp[x - t];
            }
        }
        int ans = dp.size() - 1;
        while (!dp[ans]) {
            ans--;
        }
        return ans;
    }
};

Python

from typing import List

class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        rewardValues.sort()
        dp = [False] * (rewardValues[-1] * 2)
        dp[0] = True
        for x in rewardValues:  # [0, x - 1] + x -> [x, 2x - 1]
            for i in range(x, 2 * x):  # 这里面任意一个i加上一次x后就会>2x，因此x不会被计算两次
                dp[i] |= dp[i - x]
        ans = len(dp) - 1
        while not dp[ans]:
            ans -= 1
        return ans

Go

package main

import "sort"

func maxTotalReward(rewardValues []int) int {
    sort.Ints(rewardValues)
    dp := make([]bool, 2 * rewardValues[len(rewardValues) - 1])
    dp[0] = true
    for _, x := range rewardValues {
        for i := x; i < 2 * x; i++ {
            // dp[i] = dp[i] | dp[i - x]
            // var a, b bool = true, false
            // a |= b
            // a = a | b
            if dp[i - x] {
                dp[i] = true
            }
        }
    }
    ans := len(dp) - 1
    for !dp[ans] {
        ans--
    }
    return ans
}

Java

import java.util.Arrays;

class Solution {
    public int maxTotalReward(int[] rewardValues) {
        Arrays.sort(rewardValues);
        boolean[] dp = new boolean[2 * rewardValues[rewardValues.length - 1]];
        dp[0] = true;
        for (int x : rewardValues) {
            for (int i = x; i < 2 * x; i++) {
                dp[i] |= dp[i - x];
            }
        }
        int ans = dp.length - 1;
        while (!dp[ans]) {
            ans--;
        }
        return ans;
    }
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/143314587