LeetCode 312 Burst Balloons - Implementation

Pad the array with $1$s: new_nums = [1] + nums + [1]. Now work with indices $0$ to $n+1$.

function maxCoins(nums)
    a := [1] + nums + [1]
    m := length of a
    dp := 2D array [m][m], all 0
    for gap from 2 to m - 1
        for i from 0 to m - gap - 1
            j := i + gap
            for k from i + 1 to j - 1
                coins := a[i] * a[k] * a[j] + dp[i][k] + dp[k][j]
                dp[i][j] := max(dp[i][j], coins)
    return dp[0][m-1]

The answer is $dp[0][n+1]$. Balloon $k$ is the last one burst in the interval $(i, j)$, so $a[i]$ and $a[j]$ are still present as neighbors.

Time complexity: $O(n^3)$.

Space complexity: $O(n^2)$ for the DP table.