<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>

from typing import List

# class Solution:
#     def __init__(self):
#         self.memo = {}
    
#     def solve(self, idx, curr, prev, arr1, arr2):
#         if idx == len(arr1):  # Base case: Reached the end of the arrays
#             return curr
        
#         if (idx, prev) in self.memo:
#             return self.memo[(idx, prev)]
        
#         take = 0
#         if prev == 'a':
#             take += max(self.solve(idx + 1, curr + arr1[idx], 'a', arr1, arr2), 
#                         self.solve(idx + 1, curr, 'b', arr1, arr2))
#         elif prev == 'b':
#             take += max(self.solve(idx + 1, curr + arr2[idx], 'b', arr1, arr2), 
#                         self.solve(idx + 1, curr, 'a', arr1, arr2))
        
#         self.memo[(idx, prev)] = take
#         return take
    
#     def maxEnergyBoost(self, energyDrinkA: List[int], energyDrinkB: List[int]) -> int:
#         # Start from the first element of arr1 or arr2
#         a = self.solve(1, energyDrinkA[0], 'a', energyDrinkA, energyDrinkB)
#         b = self.solve(1, energyDrinkB[0], 'b', energyDrinkA, energyDrinkB)
#         return max(a, b)


class Solution(object):
    def maxEnergyBoost(self, energyDrinkA, energyDrinkB):
        """
        :type energyDrinkA: List[int]
        :type energyDrinkB: List[int]
        :rtype: int
        """
        n = len(energyDrinkA)
        memo = {}
        def rec(i, prev):
            if i >= n:
                return 0
            if (i, prev) in memo:
                return memo[(i, prev)] 
            
            t = 0
            if prev == 0:
                t = energyDrinkA[i] + max(rec(i + 1, 0), rec(i + 2, 1))
            if prev == 1:
                t = energyDrinkB[i] + max(rec(i + 1, 1), rec(i + 2, 0))
            memo[(i, prev)] = t
            return t
        return max(rec(0, 0),  rec(0, 1))
391868