BinarySearch 0617 Candy Race Trequel

Problem statement

https://binarysearch.com/problems/Candy-Race-Trequel/

Solution

Equal to Leetcode 0312. Burst Balloons.

Complexity

Time is O(n^3), space is O(n^2).

Code

class Solution:
    def solve(self, A):
        A = [1] + A + [1]
        
        @lru_cache(None)
        def dfs(i, j):
            return max([A[i]*A[k]*A[j] + dfs(i,k) + dfs(k,j) for k in range(i+1, j)] or [0])
        
        return dfs(0, len(A) - 1)