#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/interval-dp/burst-balloons-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/interval-dp/burst-balloons-implementation

Repovive

LeetCode 312 Burst Balloons - Implementation - Interval DP | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units

Open in Course

LeetCode 312 Burst Balloons - Implementation

The code

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.

HannahHi! I'm Hannah. Let me know if you need help understanding anything!