Leetcode

Burst Balloons

May 26, 2022 by aAshish

Approach 1: Top-down

  • Time:O(n^3)
  • Space:O(n^2)

C++

 
class Solution {
 public:
  int maxCoins(vector<int>& nums) {
    const int n = nums.size();

    nums.insert(begin(nums), 1);
    nums.insert(end(nums), 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])
      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];
  }
};

JAVA

 
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];
  }
}

Python

 
class Solution:
  def maxCoins(self, nums: List[int]) -> int:
    A = [1] + nums + [1]

    @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)

C++

 
class Solution {
 public:
  int maxCoins(vector<int>& nums) {
    const int n = nums.size();

    nums.insert(begin(nums), 1);
    nums.insert(end(nums), 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];
  }
};

JAVA

 
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];
  }
}

Python

 
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]