101 Logo
onenoughtone

Code Implementation

Balloon Popping Strategy Implementation

Below is the implementation of the balloon popping strategy:

solution.js
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/**
 * Recursive Approach (Top-Down DP with Memoization)
 * Time Complexity: O(n³) - We have O(n²) different subproblems, 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
 * 
 * @param {number[]} nums - Array of balloon values
 * @return {number} - Maximum coins that can be collected
 */
function maxCoinsRecursive(nums) {
  // Add 1s at the beginning and end
  const n = nums.length;
  const newNums = new Array(n + 2);
  newNums[0] = newNums[n + 1] = 1;
  for (let i = 1; i <= n; i++) {
    newNums[i] = nums[i - 1];
  }
  
  // Initialize memoization table
  const memo = Array(n + 2).fill().map(() => Array(n + 2).fill(-1));
  
  // Recursive function to compute maximum coins
  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
    let maxCoins = 0;
    for (let k = i; k <= j; k++) {
      const coins = dp(i, k - 1) + dp(k + 1, j) + newNums[i - 1] * newNums[k] * newNums[j + 1];
      maxCoins = Math.max(maxCoins, coins);
    }
    
    // Memoize and return
    memo[i][j] = maxCoins;
    return maxCoins;
  }
  
  return dp(1, n);
}
 
/**
 * Iterative Approach (Bottom-Up DP)
 * Time Complexity: O(n³) - We have three nested loops
 * Space Complexity: O(n²) - We use a 2D DP table of size (n+2)×(n+2)
 * 
 * @param {number[]} nums - Array of balloon values
 * @return {number} - Maximum coins that can be collected
 */
function maxCoins(nums) {
  // Add 1s at the beginning and end
  const n = nums.length;
  const newNums = new Array(n + 2);
  newNums[0] = newNums[n + 1] = 1;
  for (let i = 1; i <= n; i++) {
    newNums[i] = nums[i - 1];
  }
  
  // Initialize DP table
  const dp = Array(n + 2).fill().map(() => Array(n + 2).fill(0));
  
  // Fill DP table bottom-up
  for (let len = 1; len <= n; len++) {
    for (let i = 1; i <= n - len + 1; i++) {
      const j = i + len - 1;
      for (let k = i; k <= j; k++) {
        dp[i][j] = Math.max(
          dp[i][j],
          dp[i][k - 1] + dp[k + 1][j] + newNums[i - 1] * newNums[k] * newNums[j + 1]
        );
      }
    }
  }
  
  return dp[1][n];
}
 
// Test cases
console.log(maxCoins([3, 1, 5, 8])); // 167
console.log(maxCoins([1, 5])); // 10

Step-by-Step Explanation

Let's break down the implementation:

  1. 1. Understand the Problem: First, understand that we need to find the maximum coins we can collect by bursting all balloons in the optimal order.
  2. 2. Reframe the Problem: Instead of thinking about which balloon to burst first, think about which balloon to burst last. This allows us to divide the problem into independent subproblems.
  3. 3. Add Boundary Values: Add 1s at the beginning and end of the array to handle edge cases, as specified in the problem.
  4. 4. Define the DP State: Define dp[i][j] as the maximum coins we can get by bursting all balloons from index i to j.
  5. 5. Formulate the Recurrence Relation: For each subarray from i to j, try each balloon k as the last one to burst. The maximum coins are: dp[i][j] = max(dp[i][j], dp[i][k-1] + dp[k+1][j] + nums[i-1] * nums[k] * nums[j+1]).
  6. 6. Implement the Solution: Implement either a top-down approach with memoization or a bottom-up approach to fill the DP table.
  7. 7. Test with Examples: Verify the solution with the provided examples and edge cases.
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone