Burst Balloons LeetCode solution in Python

1
class Solution:
2
    def maxCoins(self, nums):
3
        A = [1] + nums + [1]
4

5
        @lru_cache(None)
6
        def dfs(i, j):
7
            return max(
8
                [A[i] * A[k] * A[j] + dfs(i, k) + dfs(k, j) for k in range(i + 1, j)]
9
                or [0]
10
            )
11

12
        return dfs(0, len(A) - 1)