【LetMeFly】3181.执行操作可获得的最大总奖励 II:动态规划+位运算优化
力扣题目链接:https://leetcode.cn/problems/maximum-total-reward-using-operations-ii/
给你一个整数数组 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 <= 5 * 104
1 <= rewardValues[i] <= 5 * 104
解题方法:动态规划
在【LetMeFly】3180.执行操作可获得的最大总奖励 I:动态规划中,我们已经知道了 O ( m n ) O(mn) O(mn)时间复杂度的算法:
使用 d p [ i ] dp[i] dp[i]代表奖励 i i i能否获得,对于奖励数组中的一个奖励 x x x有转移公式 d p [ i ] ∣ = d p [ i − x ] dp[i] |= dp[i - x] dp[i]∣=dp[i−x],其中 0 ≤ i − x < x 0\leq i - x \lt x 0≤i−x<x。
本题增加了数据量, max ( m n ) = 50000 × 50000 = 2500000000 = 2.5 e 9 \max(mn)=50000\times 50000=2500000000=2.5e9 max(mn)=50000×50000=2500000000=2.5e9,难以在 1 1 1秒内完成计算,因此需要一些“并行计算”来降低一些时间复杂度:
不难发现,对于一个奖励 x x x我们需要从 0 0 0遍历到 x − 1 x-1 x−1,导致了 O ( m ) O(m) O(m)的时间复杂度。
但实际上, d p dp dp数组的每一个元素都是一个布尔类型的数据,我要是把这些数据拼接起来(比如原来的一个bool类型的数据变成一个整数的某一位)是不是时空复杂度直接能除以一个整数位数/计算机字长呢?
现在我们将 d p dp dp由布尔类型的数组变成一个很多位的大整数或bitset,对于 0 ≤ i < x 0\leq i\lt x 0≤i<x, d p [ i + x ] ∣ = d p [ i ] dp[i + x] |= dp[i] dp[i+x]∣=dp[i]就变成了 d p ∣ = ( d p 低 x 位左移 x 位后的结果 ) dp |= (dp低x位左移x位后的结果) dp∣=(dp低x位左移x位后的结果),因此问题就变成了如何获取 d p dp dp这个大整数的低 x x x位左移 x x x位的结果。常见方法如:
- 方法一(对于大整数):首先获得一个低 x x x位全为 1 1 1的掩码 m a s k mask mask( m a s k = ( 1 < < x ) − 1 mask = (1 << x) - 1 mask=(1<<x)−1),然后取出 d p dp dp的低 x x x位( d p & m a s k dp \& mask dp&mask),将这个结果左移 x x x位( ( d p & m a s k ) < < x (dp \& mask) << x (dp&mask)<<x)
- 方法二(对于bitset):先将 d p dp dp左移 l e n ( d p ) − x len(dp)-x len(dp)−x位再右移 l e n ( d p ) − x len(dp)-x len(dp)−x位,则除了低 x x x位以外都变成了 0 0 0,再将其左移 x x x位即可( d p < < ( l e n ( d p ) − x ) > > ( l e n ( d p ) − x ) < < x dp<<(len(dp)-x)>>(len(dp)-x)<<x dp<<(len(dp)−x)>>(len(dp)−x)<<x,等价于 d p < < ( l e n ( d p ) − x ) > > ( l e n ( d p ) − 2 x ) dp<<(len(dp)-x)>>(len(dp)-2x) dp<<(len(dp)−x)>>(len(dp)−2x))
- 时间复杂度 O ( n log n + n m / w ) O(n\log n+nm/w) O(nlogn+nm/w),其中 w w w是整数位数或计算机字长,一般为 64 64 64(或 32 32 32), max ( m n ) = 50000 × 50000 / 64 = 39 , 062 , 500 ≈ 3.9 e 7 \max(mn)=50000\times 50000/64=39,062,500\approx 3.9e7 max(mn)=50000×50000/64=39,062,500≈3.9e7
- 空间复杂度 O ( log n + m / w ) O(\log n+m/w) O(logn+m/w)
AC代码
C++
class Solution {
public:int maxTotalReward(vector<int>& rewardValues) {sort(rewardValues.begin(), rewardValues.end());bitset<100000> dp = 1; // 2 * (50000)for (int x : rewardValues) {// [0, x - 1]// dp |= dp << (100000 - x) >> (100000 - x) << x;dp |= dp << (100000 - x) >> (100000- 2 * x);}int ans = rewardValues.back() * 2 - 1;while (!dp.test(ans)) {ans--;}return ans;}
};
Python
from typing import Listclass Solution:def maxTotalReward(self, rewardValues: List[int]) -> int:rewardValues.sort()dp = 1for x in rewardValues:dp |= (dp & ((1 << x) - 1)) << xreturn dp.bit_length() - 1
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/143360617