不忘初心网站建设国内重大新闻十条

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

题干

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

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

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

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

示例 1：

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

**输出：**5

解释：

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

题解

当要切换路线的时候，付出的代价是这个格子的饮料无法获取

直接憋动态规划，当前依赖上一个位置

public static long maxEnergyBoost(int[] energyDrinkA, int[] energyDrinkB) {int length = energyDrinkA.length;long[][] dp = new long[length + 1][2];// 0为a分支   1为b分支for (int index = length - 1; index >= 0; index--) {long tmp1 = dp[index + 1][0] + energyDrinkA[index]; // 还是选择a分支long tmp2 = dp[index + 1][1];  // 切换到b分支 当前小时无法获取能量dp[index][0] = Math.max(tmp2, tmp1);long tmp3 = dp[index + 1][1] + energyDrinkB[index];// 还是选择b分支long tmp4 = dp[index + 1][0]; 切换到a分支 当前小时无法获取能量dp[index][1] = Math.max(tmp3, tmp4);}return Math.max(dp[0][0], dp[0][1]);}

进行一下优化，节省内存空间，写法抽象些

    public static long maxEnergyBoost(int[] energyDrinkA, int[] energyDrinkB) {int length = energyDrinkA.length;long aBranch = 0;long bBranch = 0;long tmp;for (int index = length - 1; index >= 0; index--) {tmp = aBranch;aBranch = Math.max(aBranch + energyDrinkA[index], bBranch);bBranch = Math.max(bBranch + energyDrinkB[index], tmp);}return Math.max(aBranch, bBranch);}

总结

常规的动态规划题目