LeetCode - 3259. 超级饮料的最大强化能量

. - 力扣（LeetCode）

题目

来自未来的体育科学家给你两个整数数组 energyDrinkA 和 energyDrinkB，数组长度都等于 n。这两个数组分别代表 A、B 两种不同能量饮料每小时所能提供的强化能量。

你需要每小时饮用一种能量饮料来 最大化 你的总强化能量。然而，如果从一种能量饮料切换到另一种，你需要等待一小时来梳理身体的能量体系（在那个小时里你将不会获得任何强化能量）。

返回在接下来的 n 小时内你能获得的 最大 总强化能量。

注意 你可以选择从饮用任意一种能量饮料开始。

• 示例 1：
  • 输入：energyDrinkA = [1,3,1], energyDrinkB = [3,1,1]
  • 输出：5
  • 解释：要想获得 5 点强化能量，需要选择只饮用能量饮料 A（或者只饮用 B）。
• 示例 2：
  • 输入：energyDrinkA = [4,1,1], energyDrinkB = [1,1,3]
  • 输出：7
  • 解释：
    • 第一个小时饮用能量饮料 A。
    • 切换到能量饮料 B ，在第二个小时无法获得强化能量。
    • 第三个小时饮用能量饮料 B ，并获得强化能量。

解题方案

每一步要么选择A，要么选择B，暴力解法是列举所有可能的序列组合。

列举所有可能的序列组合的优雅解法则是动态规划。

下面思考动态规划的状态方程：第[i]步，

初始化状态：

class Solution:
    def maxEnergyBoost(self, energyDrinkA: List[int], energyDrinkB: List[int]) -> int:
        d = [[0, 0] for _ in range(len(energyDrinkA))]
        d[0] = [energyDrinkA[0], energyDrinkB[0]]
        d[1] = [sum(energyDrinkA[0:2]), sum(energyDrinkB[0:2])]
        for i in range(2, len(energyDrinkA)):
            d[i][0] = max(d[i - 1][0], d[i - 2][1]) + energyDrinkA[i]
            d[i][1] = max(d[i - 2][0], d[i - 1][1]) + energyDrinkB[i]
        return max(d[-1])
        

分析复杂度

• 时间复杂度为计算d数组(2n元素)的时间， 

• 空间复杂度为d数组的空间2n，即

看下AI 如何

MarsCode直接用动态规划解决了这个问题。

在有固定解法或者套路的题目上，AI是可以替代人类的。