LeetCode 3259.超级饮料的最大化能力（动态规划状态机模型入门）

3259.超级饮料的最大化能力

传送门：. - 力扣（LeetCode）

来自未来的体育科学家给你两个整数数组 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 <= 10^5
• 1 <= energyDrinkA[i], energyDrinkB[i] <= 10^5

（为了方便书写这里把energyDrinkA当作a, energyDrinkB当作b）

一开始我是写了两个动态规划数组f，g,而且去表示状态的时候用了一个变量flag更新

class Solution {
    static const int N = 1e5 + 10;
    int f[N], g[N];
public:
    long long maxEnergyBoost(vector<int>& energyDrinkA, vector<int>& energyDrinkB) {
        int n = energyDrinkA.size();
        f[1] = energyDrinkA[0], f[2] = f[1] + energyDrinkA[1];
        g[1] = energyDrinkB[0], g[2] = g[1] + energyDrinkB[1];
        int flag = 1;
        for(int i = 3;i <= n;i ++){
            if(flag == 1){
                f[i] = f[i - 1] + energyDrinkA[i - 1];
                if(f[i - 2] + energyDrinkB[i - 1] > f[i]){
                    f[i] = f[i - 2] + energyDrinkB[i - 1];
                    flag = 2;
                }
            }else{
                f[i] = f[i - 1] + energyDrinkB[i - 1];
                if(f[i - 2] + energyDrinkA[i - 1] > f[i]){
                    f[i] = f[i - 2] + energyDrinkA[i - 1];
                    flag = 1;
                }
            }
        }
        flag = 2;
        for(int i = 3;i <= n;i ++){
            if(flag == 1){
                g[i] = g[i - 1] + energyDrinkA[i - 1];
                if(g[i - 2] + energyDrinkB[i - 1] > f[i]){
                    g[i] = g[i - 2] + energyDrinkB[i - 1];
                    flag = 2;
                }
            }else{
                g[i] = g[i - 1] + energyDrinkB[i - 1];
                if(g[i - 2] + energyDrinkA[i - 1] > g[i]){
                    g[i] = g[i - 2] + energyDrinkA[i - 1];
                    flag = 1;
                }
            }
        }
        return max(f[n], g[n]);
    }
};

这样很笨拙，而且错了，因为状态转移的方程推错了，这里有个误区啊，因为如果从1 -> 2之后他影响的是 状态2 的动态规划数组了，这时候跟状态1就没关系了

代码

class Solution {
    static const int N = 1e5 + 10;
    long long dp[N][2];
public:
    long long maxEnergyBoost(vector<int>& energyDrinkA, vector<int>& energyDrinkB) {
        int n = energyDrinkA.size();
        dp[1][0] = energyDrinkA[0], dp[1][1] = energyDrinkB[0];
        dp[2][0] = energyDrinkA[1] + dp[1][0], dp[2][1] = energyDrinkB[1] + dp[1][1];
        for(int i = 3;i <= n;i ++){
            dp[i][0] = max(dp[i - 1][0] + energyDrinkA[i - 1], dp[i - 2][1] + energyDrinkA[i - 1]);
            dp[i][1] = max(dp[i - 1][1] + energyDrinkB[i - 1], dp[i - 2][0] + energyDrinkB[i - 1]);
        }
        return max(dp[n][0], dp[n][1]);
    }
};

加油