力扣（leetcode）每日一题 3259 超级饮料的最大强化能量|动态规划

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);
    }

总结

常规的动态规划题目