当前位置：首页 > article >正文

day-77 超级饮料的最大强化能量

article 2024/12/25 2:39:52

在这里插入图片描述
思路
动态规划：因为每一步要么选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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。