免费英文 网站模板,网站域名如何优化,上海浦东医院网站建设,珠海门户网站建设公司问题背景
来自未来的体育科学家给你两个整数数组 e n e r g y D r i n k A energyDrinkA energyDrinkA 和 e n e r g y D r i n k B energyDrinkB energyDrinkB#xff0c;数组长度都等于 n n n。这两个数组分别代表 A A A、 B B B 两种不同能量饮料每小时所能提供的强化…问题背景
来自未来的体育科学家给你两个整数数组 e n e r g y D r i n k A energyDrinkA energyDrinkA 和 e n e r g y D r i n k B energyDrinkB energyDrinkB数组长度都等于 n n n。这两个数组分别代表 A A A、 B B B 两种不同能量饮料每小时所能提供的强化能量。 你需要每小时饮用一种能量饮料来 最大化 你的总强化能量。然而如果从一种能量饮料切换到另一种你需要等待一小时来梳理身体的能量体系在那个小时里你将不会获得任何强化能量。 返回在接下来的 n n n 小时内你能获得的 最大 总强化能量。 注意 你可以选择从饮用任意一种能量饮料开始。
数据约束 n e n e r g y D r i n k A . l e n g t h e n e r g y D r i n k B . l e n g t h n energyDrinkA.length energyDrinkB.length nenergyDrinkA.lengthenergyDrinkB.length 3 ≤ n ≤ 1 0 5 3 \le n \le 10 ^ 5 3≤n≤105 1 ≤ e n e r g y D r i n k A [ i ] , e n e r g y D r i n k B [ i ] ≤ 1 0 5 1 \le energyDrinkA[i], energyDrinkB[i] \le 10 ^ 5 1≤energyDrinkA[i],energyDrinkB[i]≤105
解题过程
题目要求从两个数组中每次选一个数累计得到最大值如果某轮将要选择与上一次选择中不同的数组中的数那么这一轮不能直接选择从另一个数组中选择。 考虑递归从前往后或者从后往前枚举都可以。每一轮选取当前值的前提是选取同一数组的上一个数或者选取不同数组的上上个数。 为了表示方便将两个数组拼成一个二维数组 e n e r g y D r i n k energyDrink energyDrink根据另一维度的下标确定从哪个数组中取值。 因此状态转移方程 d f s ( i , j ) m a x ( d f s ( i − 1 , j ) , d f s ( i − 2 , j ⊕ 1 ) ) c [ j ] [ i ] dfs(i,j) max(dfs(i − 1,j), dfs(i − 2,j \oplus 1)) c[j][i] dfs(i,j)max(dfs(i−1,j),dfs(i−2,j⊕1))c[j][i]。 递归入口 是 m a x ( d f s ( 0 , 0 ) , d f s ( 0 , 1 ) ) max(dfs(0, 0), dfs(0, 1)) max(dfs(0,0),dfs(0,1))表示选取两个数组中较大的第一个数。 递归边界 是 i e n e r g y D r i n k [ 0 ] . l e n g t h − 1 i energyDrink[0].length - 1 ienergyDrink[0].length−1表示已经选择完数组中的数。
递归的做法实现完成之后可以把它等效地翻译成递推。 答案为 m a x ( d p [ n 1 ] [ 0 ] , d p [ n 1 ] [ 1 ] ) max(dp[n 1][0], dp[n 1][1]) max(dp[n1][0],dp[n1][1])表示枚举最后一个数之后产生的最终结果。 初始值为 d p [ 0 ] [ j ] d p [ 1 ] [ j ] 0 dp[0][j]dp[1][j]0 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]);}
}梳理总结
二进制状态转换
如果一个状态变量 s t a t u s status status非零即一那么有两种方法将它转换成另一种状态 s t a t u s 1 − s t a t u s status 1 - status status1−status s t a t u s s t a t u s ⊕ 1 status status \oplus 1 statusstatus⊕1
