101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 2 main approaches to solve this problem:

  1. Recursive Approach (Top-Down DP with Memoization) - Complex approach
  2. Iterative Approach (Bottom-Up DP) - Complex approach

Approach 1: Recursive Approach (Top-Down DP with Memoization)

Let's start by understanding the problem from a different angle. Instead of thinking about which balloon to burst first, we can think about which balloon to burst last.

Thinking Process: When we burst a balloon, its adjacent balloons become adjacent to each other. This changes the structure of the problem for the remaining balloons, making it difficult to apply dynamic programming directly.

However, if we think about which balloon to burst last, we can divide the problem into independent subproblems. Let's say we have balloons from index i to j, and we decide to burst the balloon at index k last (where i ≤ k ≤ j). Then:

  • We first need to burst all balloons from i to k-1
  • We then need to burst all balloons from k+1 to j
  • Finally, we burst the balloon at index k, earning nums[i-1] * nums[k] * nums[j+1] coins

Intuition: By considering which balloon to burst last, we can divide the problem into independent subproblems and apply dynamic programming. We use memoization to avoid recalculating the same subproblems.

Algorithm:

  1. Define a recursive function maxCoins(i, j) that returns the maximum coins we can get by bursting all balloons from index i to j.
  2. For each k from i to j, consider bursting the balloon at index k last.
  3. The coins we get are: maxCoins(i, k-1) + maxCoins(k+1, j) + nums[i-1] * nums[k] * nums[j+1].
  4. Return the maximum value across all possible k.
  5. Use memoization to avoid recalculating the same subproblems.
  6. Handle edge cases by adding 1s at the beginning and end of the array.

Time Complexity:

O(n³)

We have O(n²) different subproblems (for each pair of i and j), and for each subproblem, we consider O(n) different values of k.

Space Complexity:

O(n²)

We use a memoization table of size n×n to store the results of subproblems.

Approach 2: Iterative Approach (Bottom-Up DP)

We can also solve this problem using a bottom-up dynamic programming approach, which avoids the overhead of recursion.

Thinking Process: We define dp[i][j] as the maximum coins we can get by bursting all balloons from index i to j. We fill this table bottom-up, starting from smaller subarrays and building up to larger ones.

For each subarray from i to j, we consider each balloon k (where i ≤ k ≤ j) as the last one to burst. The maximum coins we can get are:

dp[i][j] = max(dp[i][j], dp[i][k-1] + dp[k+1][j] + nums[i-1] * nums[k] * nums[j+1])

Intuition: By building solutions for smaller subarrays first, we ensure that when we calculate dp[i][j], all the required subproblems (dp[i][k-1] and dp[k+1][j]) have already been solved.

Algorithm:

  1. Create a new array with 1s at the beginning and end, and the original array in the middle.
  2. Initialize a 2D DP table dp[n+2][n+2] with all values set to 0.
  3. For each length l from 1 to n:
  4. a. For each starting index i from 0 to n-l:
  5. i. Calculate the ending index j = i+l+1.
  6. ii. For each k from i+1 to j-1:
  7. - Update dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]).
  8. Return dp[0][n+1] as the final answer.

Time Complexity:

O(n³)

We have three nested loops: one for the length of the subarray, one for the starting index, and one for the position of the last balloon to burst.

Space Complexity:

O(n²)

We use a 2D DP table of size (n+2)×(n+2) to store the results of subproblems.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function maxCoins(nums):
    // Add 1s at the beginning and end
    n = length of nums
    newNums = new array of size n+2
    newNums[0] = newNums[n+1] = 1
    for i from 1 to n:
        newNums[i] = nums[i-1]
    
    // Initialize memoization table
    memo = new 2D table of size (n+2)×(n+2) filled with -1
    
    function dp(i, j):
        // Base case: no balloons to burst
        if i > j:
            return 0
        
        // Check if already computed
        if memo[i][j] != -1:
            return memo[i][j]
        
        // Try each balloon as the last one to burst
        maxCoins = 0
        for k from i to j:
            coins = dp(i, k-1) + dp(k+1, j) + newNums[i-1] * newNums[k] * newNums[j+1]
            maxCoins = max(maxCoins, coins)
        
        // Memoize and return
        memo[i][j] = maxCoins
        return maxCoins
    
    return dp(1, n)
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone