一、题目描述

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

二、解题思路

使用动态规划的思想

状态定义：dp[i][j]：选到第 i个小时，且选择 j 饮料的最大值。j 在这里只能去 0,1 代表 A,B两种饮料。
状态转移: dp[i][0] = max(dp[i-1][0]+a[i], dp[i-1][1]); 代表 如果走到了 a[i] 这个位置，那么状态必然由 a[i-1] 或者 b[i-1] 转移过来。如果是 a[i-1] 的话，可以将 dp[i-1][0] 累加起来，因为是同种饮料。如果是 b[i-1] 的话，那么当前的这个 a[i] 实际上是不可选的，因为是饮料切换。但是可以继承 dp[i-1][1] 另一种饮料的最大值。
另一种同理。

三、代码

class Solution {public long maxEnergyBoost(int[] energyDrinkA, int[] energyDrinkB) {int size = energyDrinkB.length;long [][] dp = new long[size][2];dp[0][0] = energyDrinkA[0];dp[0][1] = energyDrinkB[0];for(int i=1;i<size;i++){// 选择A饮料   可能是从B饮料转移过来的 也可能是没有转移的dp[i][0] = Math.max(dp[i-1][0] + energyDrinkA[i],dp[i-1][1]);// 选择B饮料   可能是从A饮料转移过来的 也可能是没有转移的dp[i][1] = Math.max(dp[i-1][1] + energyDrinkB[i],dp[i-1][0]); }return Math.max(dp[size-1][0],dp[size-1][1]);  }
}