Last balloon to burst is the first balloon to build

  • 1

    It might be easier to look at this problem in a "building balloon" way, instead of "bursting balloon" way. I got this after being inspired by "last balloon to burst" solution.

    Suppose all balloons < i are already built, and all balloons > j are built. Then we need to find the first balloon to build between i and j (inclusive). So dp[i, j] = nums[i - 1] * nums[k] * nums[j + 1] + dp[i, k - 1] + dp[k + 1, j].

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.