What is the primary approach for solving the Maximum Energy Boost From Two Drinks problem?

The primary approach is using state transition dynamic programming, where you track the maximum energy boost while considering possible switches between drinks and the cleansing period.

How do I handle the cleansing time when switching between energy drinks?

In the dynamic programming approach, you account for a cleansing hour by adjusting the energy boost during transitions, ensuring no boost is gained during the switching hour.

What is the time complexity of the dynamic programming approach in this problem?

The time complexity of this approach is O(n), where n is the number of hours or length of the energy drink arrays.

Can the problem be solved using a greedy algorithm?

A greedy algorithm is not suitable for this problem because it doesn't account for the required cleansing time when switching drinks, which can lead to suboptimal solutions.

What other dynamic programming problems have a similar state transition pattern?

Problems like the 'House Robber' and 'Word Break' share a similar state transition dynamic programming approach, where you optimize decisions based on previous states.

#3259

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

超级饮料的最大强化能量

来自未来的体育科学家给你两个整数数组 energyDrinkA 和 energyDrinkB ，数组长度都等于 n 。这两个数组分别代表 A、B 两种不同能量饮料每小时所能提供的强化能量。你需要每小时饮用一种能量饮料来最大化你的总强化能量。然而，如果从一种能量饮料切换到另一种，你需要等待一小时…

数组动态规划

题目描述

来自未来的体育科学家给你两个整数数组 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 ，并获得强化能量。

提示：

n == energyDrinkA.length == energyDrinkB.length
3 <= n <= 10⁵
1 <= energyDrinkA[i], energyDrinkB[i] <= 10⁵

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][0]$ 表示在第 $i$ 小时选择能量饮料 A 获得的最大强化能量，定义 $f[i][1]$ 表示在第 $i$ 小时选择能量饮料 B 获得的最大强化能量。初始时 $f[0][0] = \textit{energyDrinkA}[0]$ , $f[0][1] = \textit{energyDrinkB}[0]$ 。答案为 $\max(f[n - 1][0], f[n - 1][1])$ 。

对于 $i > 0$ ，我们有以下状态转移方程：

\begin{aligned} f[i][0] & = \max(f[i - 1][0] + \textit{energyDrinkA}[i], f[i - 1][1]) \\ f[i][1] & = \max(f[i - 1][1] + \textit{energyDrinkB}[i], f[i - 1][0]) \end{aligned}

最后返回 $\max(f[n - 1][0], f[n - 1][1])$ 即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组的长度。

1

2

3

4

5

6

7

8

9

10

11

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate demonstrate an understanding of dynamic programming with state transitions?
question_mark
Does the candidate optimize space complexity by using only relevant states?
question_mark
Does the candidate effectively incorporate the cleansing time when switching between drinks?

warning

常见陷阱

外企场景

error
Failing to handle the cleansing period correctly when switching drinks.
error
Overcomplicating the dynamic programming approach and not optimizing space.
error
Not considering the impact of switching drinks at each step, leading to suboptimal solutions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Solving the problem with more than two energy drinks.
arrow_right_alt
Optimizing the solution further using sliding window techniques.
arrow_right_alt
Adapting the problem to handle a different number of hours or different energy drink properties.

help

常见问题

外企场景

继续练习

#3257 放三个车的价值之和最大 II #3256 放三个车的价值之和最大 I #3251 单调数组对的数目 II