力扣每日一题 3259. 超级饮料的最大强化能量

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

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

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

今天的题目又是一个动态规划；

将dpA[i]定义为最后第i个小时喝能量A的最大能量提升，如果我们只考虑前i+1个小时，那么在最后一个小时，我们喝能量饮料A。

可以得到状态转换方程 dpA[i] = max(dpA[i - 1], dpB[i - 2]) + energyDrinkA[i])

同理，我们可以定义一个dpB[i]。

那么，我们要的答案就是max(dpA[n - 1], dpB[n - 1])。

然后直接写就好了，时间复杂度O(n), 空间复杂度O(n)。

不过我们还可以再缩小一下空间，。不开数组。

class Solution {
public:
    long long maxEnergyBoost(vector<int>& energyDrinkA, vector<int>& energyDrinkB) {
        long long preA = energyDrinkA[0];
        long long preB = energyDrinkB[0];
        int len = energyDrinkA.size();
        for (int i = 1; i < len; ++i)
        {
            long long tmpA = max(preA + energyDrinkA[i], preB);
            long long tmpB = max(preB + energyDrinkB[i], preA);            
            preA = tmpA;
            preB = tmpB;
        }
        return max(preA, preB);
    }
};

时间复杂度不变，还是O(n), 但空间复杂度O(1)。