【Leetcode 每日一题 - 补卡】3259. 超级饮料的最大强化能量

问题背景

来自未来的体育科学家给你两个整数数组 $energyDrinkA$ 和 $energyDrinkB$，数组长度都等于 $n$。这两个数组分别代表 $A$、$B$ 两种不同能量饮料每小时所能提供的强化能量。
你需要每小时饮用一种能量饮料来 最大化 你的总强化能量。然而，如果从一种能量饮料切换到另一种，你需要等待一小时来梳理身体的能量体系（在那个小时里你将不会获得任何强化能量）。
返回在接下来的 $n$ 小时内你能获得的 最大 总强化能量。
注意 你可以选择从饮用任意一种能量饮料开始。

数据约束

• $n==energyDrinkA.length==energyDrinkB.length$
• $3\le n\le 10^5$
• $1\le energyDrinkA[i],energyDrinkB[i]\le 10^5$

解题过程

题目要求从两个数组中每次选一个数累计得到最大值，如果某轮将要选择与上一次选择中不同的数组中的数，那么这一轮不能直接选择从另一个数组中选择。
考虑递归，从前往后或者从后往前枚举都可以。每一轮选取当前值的前提，是选取同一数组的上一个数或者选取不同数组的上上个数。
为了表示方便，将两个数组拼成一个二维数组 $energyDrink$，根据另一维度的下标确定从哪个数组中取值。
因此，状态转移方程：$dfs(i,j)=max(dfs(i-1,j),dfs(i-2,j\oplus 1))+c[j][i]$。
递归入口 是 $max(dfs(0,0),dfs(0,1))$，表示选取两个数组中较大的第一个数。
递归边界 是 $i>energyDrink[0].length-1$，表示已经选择完数组中的数。

递归的做法实现完成之后，可以把它等效地翻译成递推。
答案为 $max(dp[n+1][0],dp[n+1][1])$，表示枚举最后一个数之后产生的最终结果。
初始值为 $dp[0][j]=dp[1][j]=0$，表示尚未枚举任何数时，状态转移数组中初始为空。

具体实现

递归

class Solution {public long maxEnergyBoost(int[] energyDrinkA, int[] energyDrinkB) {// 用原来的两个数组定义二维数组，注意一下这个写法int[][] energyDrink = {energyDrinkA, energyDrinkB};// 定义同等规模的 memo 数组用于记忆化搜索，防止炸内存long[][] memo = new long[energyDrinkA.length][2];// 递归入口， 也是答案return Math.max(dfs(0, 0, energyDrink, memo), dfs(0, 1, energyDrink, memo));}private long dfs(int i, int j, int[][] energyDrink, long[][] memo) {// 递归边界，数组下标越界范围 0if(i > energyDrink[0].length - 1) {return 0;}// 已经存储过的答案直接返回if(memo[i][j] > 0) {return memo[i][j];}// 求当前轮次的最大值并存储，注意新定义的二维数组形状，用 energyDrink[j][i] 来取值return memo[i][j] = Math.max(dfs(i + 1, j, energyDrink, memo), dfs(i + 2, j ^ 1, energyDrink, memo)) + energyDrink[j][i];}
}

递推

class Solution {public long maxEnergyBoost(int[] energyDrinkA, int[] energyDrinkB) {int n = energyDrinkA.length;// 定义状态转移数组 dp，由于状态可能和上上个数有关，数组规模需要相应地扩大long[][] dp = new long[n + 2][2];for(int i = 0; i < n; i++) {dp[i + 2][0] = Math.max(dp[i + 1][0], dp[i][1]) + energyDrinkA[i];dp[i + 2][1] = Math.max(dp[i + 1][1], dp[i][0]) + energyDrinkB[i];}return Math.max(dp[n + 1][0], dp[n + 1][1]);}
}

梳理总结

二进制状态转换

如果一个状态变量$status$非零即一，那么有两种方法将它转换成另一种状态：

• $status=1-status$
• $status=status\oplus 1$