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
28
29
30
class Solution {
 public:
  int maxCoins(vector<int>& nums) {
    const int n = nums.size();

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

    // dp[i][j] := maxCoins(nums[i..j])
    dp.resize(n + 2, vector<int>(n + 2));
    return maxCoins(nums, 1, n);
  }

 private:
  vector<vector<int>> dp;

  int maxCoins(vector<int>& nums, int i, int j) {
    if (i > j)
      return 0;
    if (dp[i][j] > 0)
      return dp[i][j];

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

    return dp[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
28
29
30
31
32
class Solution {
  public int maxCoins(int[] nums) {
    final int n = nums.length;

    A = new int[n + 2];

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

    // dp[i][j] := maxCoins(A[i..j])
    dp = new int[n + 2][n + 2];
    return maxCoins(1, n);
  }

  private int[][] dp;
  private int[] A;

  private int maxCoins(int i, int j) {
    if (i > j)
      return 0;
    if (dp[i][j] > 0)
      return dp[i][j];

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

    return dp[i][j];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def maxCoins(self, nums: List[int]) -> int:
    A = [1] + nums + [1]

    @functools.lru_cache(None)
    def dp(i: int, j: int) -> int:
      if i > j:
        return 0

      return max(dp(i, k - 1) + dp(k + 1, j) + A[i - 1] * A[k] * A[j + 1]
                 for k in range(i, j + 1))

    return dp(1, len(nums))

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
23
class Solution {
 public:
  int maxCoins(vector<int>& nums) {
    const int n = nums.size();

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

    // dp[i][j] := maxCoins(nums[i..j])
    vector<vector<int>> dp(n + 2, vector<int>(n + 2));

    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;
    int[] A = new int[n + 2];
    System.arraycopy(nums, 0, A, 1, n);
    A[0] = 1;
    A[n + 1] = 1;

    // dp[i][j] := maxCoins(A[i..j])
    int[][] dp = new int[n + 2][n + 2];

    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
class Solution:
  def maxCoins(self, nums: List[int]) -> int:
    n = len(nums)
    A = [1] + nums + [1]
    dp = [[0] * (n + 2) for _ in range(n + 2)]

    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] +
              A[i - 1] * A[k] * A[j + 1])

    return dp[1][n]