跳转至

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

#python #leetcode #dp

题目描述

关联：https://leetcode.cn/problems/maximum-energy-boost-from-two-drinks/description

题目描述

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

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

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

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

本题的范围：

\(n = \text{energyDrinkA.length} = \text{energyDrinkB.length}\)

\(3 \leq n \leq 10^5\)

\(1 \leq \text{energyDrinkA}[i], \text{energyDrinkB}[i] \leq 10^5\)

这个题目描述其实有一点问题。它给出了饮料的数组，但是并没有说明是按照数组下标顺序来喝还是可以在数组中任意选择一个饮料来喝。

如果是可以随便选，那当然是直接贪心秒了（先从大到小排序，然后每次选择最大的）。但是这个题没有说，那就把它当作是按下标顺序来喝吧。

解题思路

动态规划秒了。

我们可以定义两个数组 dpA 和 dpB，分别表示在第 i 小时选择饮用 A 或 B 能量饮料时的最大强化能量。

具体步骤如下：

  1. 初始化 dpA[0] 为 energyDrinkA[0]，dpB[0] 为 energyDrinkB[0]，表示在第一个小时选择饮用 A 或 B 能量饮料的强化能量。

  2. 从第 1 小时开始，逐步计算每个小时选择饮用 A 或 B 能量饮料的最大强化能量：

  3. 如果选择饮用 A 能量饮料，则可以从前一个小时选择饮用 A 或 B 能量饮料中选择最大值，但如果前一个小时选择饮用 B，则需要等待一小时。

  4. 同理，如果选择饮用 B 能量饮料，则可以从前一个小时选择饮用 A 或 B 能量饮料中选择最大值，但如果前一个小时选择饮用 A，则需要等待一小时。

  5. 最终结果为 dpA[n-1] 和 dpB[n-1] 中的最大值。

完整题解

class Solution:
    def maxEnergyBoost(self, energyDrinkA: list[int], energyDrinkB: list[int]) -> int:
        n = len(energyDrinkA)
        dpA = [0] * n
        dpB = [0] * n

        dpA[0] = energyDrinkA[0]
        dpB[0] = energyDrinkB[0]

        for i in range(1, n):
            dpA[i] = max(dpA[i-1], dpB[i-1] - energyDrinkB[i-1]) + energyDrinkA[i]
            dpB[i] = max(dpB[i-1], dpA[i-1] - energyDrinkA[i-1]) + energyDrinkB[i]

        return max(dpA[n-1], dpB[n-1])

复杂度分析

时间复杂度：\(O(n)\)

空间复杂度：\(O(n)\)

评论