当前位置：首页 > article >正文

LeetCode：3259. 超级饮料的最大强化能量（DP Java）

article 2024/11/5 1:26:10

3259. 超级饮料的最大强化能量

题目描述：

实现代码与解析：

原理思路：

3259. 超级饮料的最大强化能量

题目描述：

来自未来的体育科学家给你两个整数数组 energyDrinkA 和 energyDrinkB，数组长度都等于 n。这两个数组分别代表 A、B 两种不同能量饮料每小时所能提供的强化能量。

你需要每小时饮用一种能量饮料来 最大化 你的总强化能量。然而，如果从一种能量饮料切换到另一种，你需要等待一小时来梳理身体的能量体系（在那个小时里你将不会获得任何强化能量）。

返回在接下来的 n 小时内你能获得的最大总强化能量。

注意你可以选择从饮用任意一种能量饮料开始。

示例 1：

输入：energyDrinkA = [1,3,1], energyDrinkB = [3,1,1]

输出：5

解释：

要想获得 5 点强化能量，需要选择只饮用能量饮料 A（或者只饮用 B）。

示例 2：

输入：energyDrinkA = [4,1,1], energyDrinkB = [1,1,3]

输出：7

解释：

第一个小时饮用能量饮料 A。
切换到能量饮料 B ，在第二个小时无法获得强化能量。
第三个小时饮用能量饮料 B ，并获得强化能量。

提示：

n == energyDrinkA.length == energyDrinkB.length
3 <= n <= 105
1 <= energyDrinkA[i], energyDrinkB[i] <= 105

实现代码与解析：

DP

class Solution {
    public long maxEnergyBoost(int[] energyDrinkA, int[] energyDrinkB) {

        int n = energyDrinkA.length;
        long[][] f = new long[n][2];

        f[0][0] = energyDrinkA[0];
        f[0][1] = energyDrinkB[0];

/*        f[1][0] = Math.max(energyDrinkB[1], energyDrinkA[0] + energyDrinkA[1]);
        f[1][1] = Math.max(energyDrinkA[1], energyDrinkB[0] + energyDrinkB[1]);*/
        f[1][0] = energyDrinkA[0] + energyDrinkA[1];
        f[1][1] = energyDrinkB[0] + energyDrinkB[1];
        for (int i = 2; i < n; i++) {
            f[i][0] = Math.max(f[i - 1][0], f[i - 2][1]) + energyDrinkA[i];
            f[i][1] = Math.max(f[i - 1][1], f[i - 2][0]) + energyDrinkB[i];
        }

        return Math.max(f[n - 1][0], f[n - 1][1]);
    }
}

原理思路：

从索引 2 开始到数组长度 n - 1 进行循环，用于逐步计算 f 数组每一行的值。
对于 f[i][0]：
- 它通过取 f 数组中前一个位置（i - 1）的第一列的值 f[i - 1][0] 和再往前一个位置（i - 2）的第二列的值 f[i - 2][1] 两者中的最大值，然后加上 energyDrinkA 数组当前位置（索引为 i）的元素来更新自身。这意味着当前选择 energyDrinkA 数组第 i 个元素时的最大能量值，取决于前一步选择 energyDrinkA 相关的最大能量（f[i - 1][0]）或者是再前一步选择 energyDrinkB 相关且转换到当前与 energyDrinkA 结合的最大能量（f[i - 2][1]）。
对于 f[i][1]：
- 与 f[i][0] 的计算逻辑类似，只是对应的列和数组不同。它取 f 数组中前一个位置（i - 1）的第二列的值 f[i - 1][1] 和再往前一个位置（i - 2）的第一列的值 f[i - 2][0] 两者中的最大值，再加上 energyDrinkB 数组当前位置（索引为 i）的元素来更新自身。即当前选择 energyDrinkB 数组第 i 个元素时的最大能量值，取决于前一步选择 energyDrinkB 相关的最大能量（f[i - 1][1]）或者是再前一步选择 energyDrinkA 相关且转换到当前与 energyDrinkB 结合的最大能量（f[i - 2][0]）。