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)$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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


3180.执行操作可获得的最大总奖励 I
https://blog.letmefly.xyz/2024/10/28/LeetCode 3180.执行操作可获得的最大总奖励I/
作者
Tisfy
发布于
2024年10月28日
许可协议