Skip to content

312. Burst Balloons 👍

Approach 1: Top-down

  • Time: $O(n^3)$
  • Space: $O(n^2)$
 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
class Solution {
 public:
  int maxCoins(vector<int>& nums) {
    const int n = nums.size();
    vector<vector<int>> mem(n + 2, vector<int>(n + 2));
    nums.insert(nums.begin(), 1);
    nums.insert(nums.end(), 1);
    return maxCoins(nums, 1, n, mem);
  }

 private:
  // Returns maxCoins(nums[i..j]).
  int maxCoins(const vector<int>& nums, int i, int j,
               vector<vector<int>>& mem) {
    if (i > j)
      return 0;
    if (mem[i][j] > 0)
      return mem[i][j];

    for (int k = i; k <= j; ++k)
      mem[i][j] = max(mem[i][j], maxCoins(nums, i, k - 1, mem) +
                                     maxCoins(nums, k + 1, j, mem) +
                                     nums[i - 1] * nums[k] * nums[j + 1]);

    return mem[i][j];
  }
};

 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
class Solution {
  public int maxCoins(int[] nums) {
    final int n = nums.length;
    int[][] mem = new int[n + 2][n + 2];
    int[] extendedNums = new int[n + 2];
    System.arraycopy(nums, 0, extendedNums, 1, n);
    extendedNums[0] = 1;
    extendedNums[n + 1] = 1;
    return maxCoins(extendedNums, 1, n, mem);
  }

  // Returns maxCoins(nums[i..j]).
  private int maxCoins(int[] nums, int i, int j, int[][] mem) {
    if (i > j)
      return 0;
    if (mem[i][j] > 0)
      return mem[i][j];

    for (int k = i; k <= j; ++k)
      mem[i][j] = Math.max(mem[i][j],                          //
                           maxCoins(nums, i, k - 1, mem) +     //
                               maxCoins(nums, k + 1, j, mem) + //
                               nums[i - 1] * nums[k] * nums[j + 1]);

    return mem[i][j];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def maxCoins(self, nums: list[int]) -> int:
    n = len(nums)
    nums = [1] + nums + [1]

    @functools.lru_cache(None)
    def dp(i: int, j: int) -> int:
      """Returns maxCoins(nums[i..j])."""
      if i > j:
        return 0
      return max(dp(i, k - 1) +
                 dp(k + 1, j) +
                 nums[i - 1] * nums[k] * nums[j + 1]
                 for k in range(i, j + 1))

    return dp(1, n)

Approach 2: Bottom-up

  • Time: $O(n^3)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int maxCoins(vector<int>& nums) {
    const int n = nums.size();
    // dp[i][j] := maxCoins(nums[i..j])
    vector<vector<int>> dp(n + 2, vector<int>(n + 2));

    nums.insert(nums.begin(), 1);
    nums.insert(nums.end(), 1);

    for (int d = 0; d < n; ++d)
      for (int i = 1; i + d <= n; ++i) {
        const int j = i + d;
        for (int k = i; k <= j; ++k)
          dp[i][j] = max(dp[i][j],                      //
                         dp[i][k - 1] + dp[k + 1][j] +  //
                             nums[i - 1] * nums[k] * nums[j + 1]);
      }

    return dp[1][n];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int maxCoins(int[] nums) {
    final int n = nums.length;
    // dp[i][j] := maxCoins(A[i..j])
    int[][] dp = new int[n + 2][n + 2];
    int[] A = new int[n + 2];

    System.arraycopy(nums, 0, A, 1, n);
    A[0] = 1;
    A[n + 1] = 1;

    for (int d = 0; d < n; ++d)
      for (int i = 1; i + d <= n; ++i) {
        final int j = i + d;
        for (int k = i; k <= j; ++k)
          dp[i][j] = Math.max(dp[i][j],                     //
                              dp[i][k - 1] + dp[k + 1][j] + //
                                  A[i - 1] * A[k] * A[j + 1]);
      }

    return dp[1][n];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def maxCoins(self, nums: list[int]) -> int:
    n = len(nums)
    # dp[i][j] := maxCoins(nums[i..j])
    dp = [[0] * (n + 2) for _ in range(n + 2)]

    nums = [1] + nums + [1]

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

    return dp[1][n]