Burst Balloons

'''
Intuitive approach:
Initial state: 1  A B C D E F G 1 ( ALL FILLED)
Main problem def'n: Burst a contiguous subarray of ballons from index 1 to 7 with initial bounds 1, 1 in most profitable way. (Lower bound is closest yet filled balloon to left of subarray and upper bound is closest yet filled balloon to the right of subarray)
To start with it we have 7 choices for the first ballon.
Lets start with bursting fourth balloon D first which gives us C*D*E coins. Now our next task is to burst two subarrays 1:3 and 5:7, however the upper bound of first subarray is not yet defined (it can be E or F or G), similiarly the lower bound of second subarray is not fixed (it could be C or B or A). Thus this division is not valid as the subproblems are not defined and are not independent of each other

Correct Approach:
Lets reverse the task with same example as:
Initial state: 1 A B C D E F G 1 ( ALL BURSTED)
Main problem def'n: Fill a contiguous subarray of balloons from index 1 to 7 with initial bounds 1, 1 in most profitable way.
To start with it we have 7 choices for the first balloon.
Lets start with filling fourth balloon D which gives us 1*D*1 coins. Now our next task is to fill two subarrays 1:3 and 5:7. The lower and upper bound of first subarray are 1 and D while that of the second subarray are D and 1. Thus this is valid division as subproblems are clearly defined and independent.
We do the same task by starting with six other ballons and take the max of them as the answer.

Thus:
Dp[i][j]: max coins obtained by filling a contiguous subarray of length i starting at index j with bounds nums[j-1], nums[j+i].
..., Nums[j-1], (Nums[j], ..., Nums[j+i-1]), nums[j+i], ...
To calculate dp[i][j] we have k options(0<=k<i) in each of them we choose kth balloon in the subarray to be filled first(i.e  balloon at j+k index as subarray starts at index j).
After fixing k, we get lower_bound*nums[j+k]*upper_bound (i.e nums[j-1]*nums[j+k]*nums[j+i]) coins and then we have to recursively solve for subarrays nums[j:k-1] and nums[k+1:j+i-1]:
..., Nums[j-1], (Nums[j], ..., Nums[j+k-1]), Nums[j+k], (Nums[j+k+1], ..., Nums[j+i-1]), nums[j+i], ...,
Dp[i][j] = nums[j-1]*nums[j+k]*nums[j+i] + Dp[k][j] + Dp[i-1-k][j+k+1]...vary k from 0 to i and take max
Base case: for i=0 0<=j<=n dp[i][j] = 0 (No balloons to fill)
'''

"""
Bottom up approach: O(n3)
Length of subarray(i=0, N) --> Starting point(j=0, N-i) --> Splitting point(first balloon to fill in subarray)
"""
class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        n = len(nums)
        nums = nums+[1]
        dp = [[0]*(n+1) for _  in range(n+1)]

        for i in range(1, n+1):
            for j in range(n+1-i): #nums[j:j+i]
                for k in range(i):
                    dp[i][j] = max(dp[i][j], dp[k][j]+nums[j-1]*nums[j+k]*nums[j+i]+dp[i-1-k][j+k+1])

        return dp[n][0]