<p>You are given two integer arrays <code>energyDrinkA</code> and <code>energyDrinkB</code> of the same length <code>n</code> by a futuristic sports scientist. These arrays represent the energy boosts per hour provided by two different energy drinks, A and B, respectively.</p>

<p>You want to <em>maximize</em> your total energy boost by drinking one energy drink <em>per hour</em>. However, if you want to switch from consuming one energy drink to the other, you need to wait for <em>one hour</em> to cleanse your system (meaning you won&#39;t get any energy boost in that hour).</p>

<p>Return the <strong>maximum</strong> total energy boost you can gain in the next <code>n</code> hours.</p>

<p><strong>Note</strong> that you can start consuming <em>either</em> of the two energy drinks.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> energyDrinkA<span class="example-io"> = [1,3,1], </span>energyDrinkB<span class="example-io"> = [3,1,1]</span></p>

<p><strong>Output:</strong> <span class="example-io">5</span></p>

<p><strong>Explanation:</strong></p>

<p>To gain an energy boost of 5, drink only the energy drink A (or only B).</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> energyDrinkA<span class="example-io"> = [4,1,1], </span>energyDrinkB<span class="example-io"> = [1,1,3]</span></p>

<p><strong>Output:</strong> <span class="example-io">7</span></p>

<p><strong>Explanation:</strong></p>

<p>To gain an energy boost of 7:</p>

<ul>
	<li>Drink the energy drink A for the first hour.</li>
	<li>Switch to the energy drink B and we lose the energy boost of the second hour.</li>
	<li>Gain the energy boost of the drink B in the third hour.</li>
</ul>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == energyDrinkA.length == energyDrinkB.length</code></li>
	<li><code>3 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= energyDrinkA[i], energyDrinkB[i] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def __init__(self):
        self._cache = {}
        
    def getMaxAtIndex(self, idx, A, B, cur, curEnergy):
        if idx >= len(A):
            return curEnergy
        
        if (idx, cur) in self._cache:
            return self._cache[(idx, cur)]
        
        if cur == 'A':
            self._cache[(idx, cur)] = max(
                self.getMaxAtIndex(idx + 1, A, B, cur, curEnergy + A[idx]),
                self.getMaxAtIndex(idx + 1, A, B, 'B', curEnergy)
            )
        else:
            self._cache[(idx, cur)] = max(
                self.getMaxAtIndex(idx + 1, A, B, cur, curEnergy + B[idx]),
                self.getMaxAtIndex(idx + 1, A, B, 'A', curEnergy)
            )
            
        return self._cache[(idx, cur)]
    
    def maxEnergyBoost2(self, energyDrinkA: List[int], energyDrinkB: List[int]) -> int:
        return max(
            self.getMaxAtIndex(1, energyDrinkA, energyDrinkB, 'A', energyDrinkA[0]),
            self.getMaxAtIndex(1, energyDrinkA, energyDrinkB, 'B', energyDrinkB[0])
        )
    
    def maxEnergyBoost(self, energyDrinkA, energyDrinkB):
        n = len(energyDrinkA)

        # Memoization dictionary
        memo = {}

        def max_energy(hour, last_drink):
            # Base case: if we have exceeded the hours
            if hour >= n:
                return 0

            # Check if this state has already been computed
            if (hour, last_drink) in memo:
                return memo[(hour, last_drink)]

            if last_drink == 0:  # Last drink was A
                take_A = energyDrinkA[hour] + max_energy(hour + 1, 0)
                skip_to_B = max_energy(hour + 1, 1)
                result = max(take_A, skip_to_B)

            elif last_drink == 1:  # Last drink was B
                take_B = energyDrinkB[hour] + max_energy(hour + 1, 1)
                skip_to_A = max_energy(hour + 1, 0)
                result = max(take_B, skip_to_A)

            else:  # No last drink, can start with either
                start_with_A = energyDrinkA[hour] + max_energy(hour + 1, 0)
                start_with_B = energyDrinkB[hour] + max_energy(hour + 1, 1)
                result = max(start_with_A, start_with_B)

            # Store the result in the memo dictionary
            memo[(hour, last_drink)] = result
            return result

        # Start from hour 0 with no previous drink (-1)
        return max_energy(0, -1)
        
        
2341