[leetcode每日一题] 3259. 超级饮料的最大强化能量

yyyyye

一道很简单的动态规划。

动态规划解法

定义状态空间：
dp[i][j]表示选择i瓶饮料j时，最大获得的强化能量。
其中，$0 \leq i \leq n$；当$j=0$时，表示饮料A，当$j=1$时，表示饮料B。
状态转移方程：
dp[i][0] = max{dp[i - 1][0], dp[i - 2][1]} + A[i - 1]
dp[i][1] = max{dp[i - 1][1], dp[i - 2][0]} + B[i - 1]

代码：

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

复杂度分析：
时间复杂度$O(n)$，空间复杂度$O(n)$

动态规划+滑动数组解法

滑动数组优化：
考虑到i状态转换的过程中只与i-1和i-2状态有关，可以使用滑动数组进行优化，这里采用cur和pre对于当前状态和上一状态进行记录，tmp用于状态转移过程中cur数据的临时存储。

代码：

class Solution {
public:
    long long maxEnergyBoost(vector<int>& energyDrinkA, vector<int>& energyDrinkB) {
        int n = energyDrinkA.size();
        vector<long long> pre(2, 0), cur(2, 0), tmp(2, 0);
        for(int i = 1; i <= n; i++)
        {
            tmp[0] = cur[0], tmp[1] = cur[1];
            cur[0] = max(cur[0], pre[1]) + energyDrinkA[i - 1];
            cur[1] = max(cur[1], pre[0]) + energyDrinkB[i - 1];
            pre[0] = tmp[0], pre[1] = tmp[1];
        }
        return max(cur[1], cur[0]);
    }
};

复杂度分析：
时间复杂度$O(n)$，空间复杂度$O(1)$

Zero_canyon

public:
    long long maxEnergyBoost(vector<int>& energyDrinkA, vector<int>& energyDrinkB) {
        int n = energyDrinkA.size();
        long long int energy = 0;
        auto &a = energyDrinkA, &b = energyDrinkB;
        long long int i = 0,ii=0;
        for(int j = 0;j < n;j++)
        {
            i += a[j];
            ii += b[j];
            if(j >= 2)
            {
                long long int iii = i;
                i = max(i, ii-b[j-1]-b[j]+a[j]);
                ii = max(ii, iii-a[j-1]-a[j]+b[j]);
            }
        }
        energy=(i > ii?i:ii)
        return energy;
    }
};```
虽然看不懂ye的
在理解ye上进行的

xxingyu

/*
 * @lc app=leetcode.cn id=3259 lang=cpp
 *
 * [3259] 超级饮料的最大强化能量
 */
#include <bits/stdc++.h>
using namespace std;
// @lc code=start
class Solution {
 public:
  using i64 = long long;
  long long maxEnergyBoost(vector<int>& energyDrinkA,
                           vector<int>& energyDrinkB) {
    int n = energyDrinkA.size();
    vector<i64> dp(3, 0);
    for (int i = 0; i < n; i++) {
      dp[0] = max(dp[0] + energyDrinkA[i], dp[1]);
      dp[1] = max(dp[1] + energyDrinkB[i], dp[2]);
      dp[2] = dp[0];
    }
    return max(dp[0], dp[1]);
  }
};
// @lc code=end