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

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

思路

起初我想用$O(n)$时间复杂度的动态规划，但是这样做对于有些用例会得到错误答案。后面看到提示，动态规划可以用来表示某一个值能否取到，学习到了新的解法。

首先我们将数组排序，以保证后面的元素总比前面的元素大。用一个一维动态数组表示当前数组长度下，某一个当前总奖励是否能够取到。同时我们保存一个当前最大值，在小于rewardValues[i]的总奖励中，如果某个值可以取到，就更新dp[rewardValues[i] + j]为可以取到，并可以尝试更新最大值。最后返回最大值即可。

布尔值dp

当dp的值设为数值类型时难以求解时，我们可以考虑把数值类型作为数组的下标，转而把是否选取的状态设为dp的值，这样我们就可以方便地遍历所有值。

也就是说遍历状态难以求解时，可以尝试遍历值，这也是一种新思路。

复杂度

• 时间复杂度: $O(nm)$
• 空间复杂度: $O(n)$

Code

class Solution {
    public int maxTotalReward(int[] rewardValues) {
        Arrays.sort(rewardValues);
        int n = rewardValues.length;
        boolean dp[] = new boolean [rewardValues[n - 1] * 2];
        dp[rewardValues[0]] = true;
        int max = rewardValues[0];
        for (int i = 1; i < n; i++) {
            dp[rewardValues[i]] = true;
            for (int j = 0; j < rewardValues[i]; j++) {
                if (dp[j] == true) {
                    dp[rewardValues[i] + j] = true;
                    max = rewardValues[i] + j;
                }
            }
        }
        return max;
    }
}