思路
动态规划:因为每一步要么选A,要么选B,所以问题可以转换为求最后一步从A选或从B选中的较大值
解题过程
定义而二维数组dp,dp[i][0]表示最后一步从A取能获得的最大能量,dp[i][1]表示最后一步从B取能获得的最大能量状态转换方程为:
dp[i][0]=Math.max(dp[i-1][0]+energyDrinkA[i],dp[i-1][1])
dp[i][1]=Math.max(dp[i-1][1]+energyDrinkB[i],dp[i-1][0])
最后返回Math.max(dp[len-1][0],dp[len-1][1])即可
Code
class Solution {
public long maxEnergyBoost(int[] energyDrinkA, int[] energyDrinkB) {
int len=energyDrinkA.length;
long dp[][]=new long[len][2];
dp[0][0]=energyDrinkA[0];
dp[0][1]=energyDrinkB[0];
for(int i=1;i<len;i++){
dp[i][0]=Math.max(dp[i-1][0]+energyDrinkA[i],dp[i-1][1]);
dp[i][1]=Math.max(dp[i-1][1]+energyDrinkB[i],dp[i-1][0]);
}
return Math.max(dp[len-1][0],dp[len-1][1]);
}
}
作者:菜卷
链接:https://leetcode.cn/problems/maximum-energy-boost-from-two-drinks/solutions/2974033/chao-ji-yin-liao-de-zui-da-qiang-hua-nen-vef1/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。