問題背景

來自未來的體育科學(xué)家給你兩個整數(shù)數(shù)組 $energyDrinkA$ 和 $energyDrinkB$，數(shù)組長度都等于 $n$。這兩個數(shù)組分別代表 $A$、$B$ 兩種不同能量飲料每小時所能提供的強化能量。
你需要每小時飲用一種能量飲料來 最大化 你的總強化能量。然而，如果從一種能量飲料切換到另一種，你需要等待一小時來梳理身體的能量體系（在那個小時里你將不會獲得任何強化能量）。
返回在接下來的 $n$ 小時內(nèi)你能獲得的 最大 總強化能量。
注意 你可以選擇從飲用任意一種能量飲料開始。

數(shù)據(jù)約束

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

解題過程

題目要求從兩個數(shù)組中每次選一個數(shù)累計得到最大值，如果某輪將要選擇與上一次選擇中不同的數(shù)組中的數(shù)，那么這一輪不能直接選擇從另一個數(shù)組中選擇。
考慮遞歸，從前往后或者從后往前枚舉都可以。每一輪選取當(dāng)前值的前提，是選取同一數(shù)組的上一個數(shù)或者選取不同數(shù)組的上上個數(shù)。
為了表示方便，將兩個數(shù)組拼成一個二維數(shù)組 $energyDrink$，根據(jù)另一維度的下標(biāo)確定從哪個數(shù)組中取值。
因此，狀態(tài)轉(zhuǎn)移方程：$dfs(i,j)=max(dfs(i?1,j),dfs(i?2,j\oplus 1))+c[j][i]$。
遞歸入口 是 $max(dfs(0,0),dfs(0,1))$，表示選取兩個數(shù)組中較大的第一個數(shù)。
遞歸邊界 是 $i>energyDrink[0].length?1$，表示已經(jīng)選擇完數(shù)組中的數(shù)。

遞歸的做法實現(xiàn)完成之后，可以把它等效地翻譯成遞推。
答案為 $max(dp[n+1][0],dp[n+1][1])$，表示枚舉最后一個數(shù)之后產(chǎn)生的最終結(jié)果。
初始值為 $dp[0][j]=dp[1][j]=0$，表示尚未枚舉任何數(shù)時，狀態(tài)轉(zhuǎn)移數(shù)組中初始為空。

具體實現(xiàn)

遞歸

class Solution {public long maxEnergyBoost(int[] energyDrinkA, int[] energyDrinkB) {// 用原來的兩個數(shù)組定義二維數(shù)組，注意一下這個寫法int[][] energyDrink = {energyDrinkA, energyDrinkB};// 定義同等規(guī)模的 memo 數(shù)組用于記憶化搜索，防止炸內(nèi)存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) {// 遞歸邊界，數(shù)組下標(biāo)越界范圍 0if(i > energyDrink[0].length - 1) {return 0;}// 已經(jīng)存儲過的答案直接返回if(memo[i][j] > 0) {return memo[i][j];}// 求當(dāng)前輪次的最大值并存儲，注意新定義的二維數(shù)組形狀，用 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;// 定義狀態(tài)轉(zhuǎn)移數(shù)組 dp，由于狀態(tài)可能和上上個數(shù)有關(guān)，數(shù)組規(guī)模需要相應(yīng)地擴大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]);}
}

梳理總結(jié)

二進制狀態(tài)轉(zhuǎn)換

如果一個狀態(tài)變量$status$非零即一，那么有兩種方法將它轉(zhuǎn)換成另一種狀態(tài)：

• $status=1?status$
• $status=status\oplus 1$