BinarySearch 0662 Maximum Additive Score by Removing Numbers

Problem statement

https://binarysearch.com/problems/Maximum-Additive-Score-by-Removing-Numbers/

Solution

Variation of Leetcode 0312. Burst Balloons.

Complexity

It is O(n^3) for time and O(n^2) for space.

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(1, len(A) - 2)