LeetCode|3180. 执行操作可获得的最大总奖励 I(day23)

作者：MJ昊

博客：掘金、CSDN等

公众号：程序猿的编程之路

今天是 昊 的算法之路第23天，今天分享的是LeetCode第3180题执行操作可获得的最大总奖励 I的解题思路。这是一道中等难度的题目，要求我们在给定的奖励值数组中，通过某些操作尽可能获取最大总奖励。

题目描述简要回顾

题目要求从一个数组rewardValues中选择部分值，使得这些值相加可以尽可能获得最大的总和。同时我们要考虑到一些操作限制，确保总和符合特定规则或范围。

解题思路

1. 排序处理：先对 rewardValues 数组进行升序排列，以便我们从小到大依次尝试累积奖励值。
2. 动态规划数组：使用一个dp数组来标记哪些奖励和是可行的。dp[i]为 1 表示可以通过某些操作获得和为i的总奖励。
3. 倒序遍历：从最大可能的范围向下更新dp，确保每次累加时避免重复计算。
4. 结果计算：最后遍历dp数组，找出最大的可行奖励和。

代码实现：

var maxTotalReward = function (rewardValues) {
    rewardValues.sort((a, b) => a - b);// 对奖励值数组进行排序
    const m = rewardValues[rewardValues.length - 1]; // 找到最大奖励值
    const dp = Array(m * 2).fill(0);// 初始化动态规划数组
    dp[0] = 1;// 初始状态：和为 0 是可行的
    // 遍历奖励值，并倒序更新 dp 数组
    for (let x of rewardValues) {
        for (let k = 2 * x - 1; k >= x; k--) {
            if (dp[k - x] === 1) {
                dp[k] = 1;// 如果减去 x 后可行，则当前和也可行
            }
        }
    }
    // 找到最大的可行奖励和
    let res = 0;
    for (let i = 0; i < dp.length; i++) {
        if (dp[i] === 1) {
            res = i;
        }
    }
    return res;
};

总结

本题采用排序结合动态规划的方法，通过倒序遍历避免重复累加，从而有效计算出最大可行的奖励和。通过合理地更新 dp 数组，我们可以保证解法的高效性。在面临类似的求解最大和问题时，这种思路具有很强的通用性。