Sponsored
Sponsored
This approach involves using a recursive function to try bursting each balloon and calculating the coins collected, while storing results of already computed subproblems to avoid redundant calculations. We pad the nums array with 1 at both ends to handle boundary conditions easily. For each subproblem defined by indices left and right, we choose a balloon i to burst last and calculate the coins.
Time Complexity: O(n^3), where n is the total number of balloons including the padding ones.
Space Complexity: O(n^2) due to memoization table.
1function maxCoins(nums) {
2 const n = nums.length;
3 nums = [1, ...nums, 1];
4 const memo = Array.from({ length: n + 2 }, () => Array(n + 2).fill(0));
5
6 function dp(left, right) {
7 if (left + 1 === right) return 0;
8 if (memo[left][right] > 0) return memo[left][right];
9 let ans = 0;
10 for (let i = left + 1; i < right; i++) {
11 ans = Math.max(ans, nums[left] * nums[i] * nums[right] + dp(left, i) + dp(i, right));
12 }
13 memo[left][right] = ans;
14 return ans;
15 }
16
17 return dp(0, n + 1);
18}This JavaScript solution adopts the same approach. Dynamic programming with a recursive function dp is utilized to explore all options. Base case and memoization are similarly handled.
In this approach, we use a DP table to systematically build up solutions from smaller problems to a larger one without recursion. We create a dynamic programming matrix dp where dp[left][right] indicates the max coins to be obtained from subarray nums[left:right]. For each subarray defined by len, we consider bursting each possible k as the last balloon and compute the result using previously computed results.
Time Complexity: O(n^3)
Space Complexity: O(n^2)
1public class Solution {
public int MaxCoins(int[] nums) {
int n = nums.Length;
int[] numsWithBoundaries = new int[n + 2];
System.Array.Copy(nums, 0, numsWithBoundaries, 1, n);
numsWithBoundaries[0] = numsWithBoundaries[n + 1] = 1;
int[,] dp = new int[n + 2, n + 2];
for (int length = 3; length <= n + 2; length++) {
for (int left = 0; left <= n + 2 - length; left++) {
int right = left + length;
for (int k = left + 1; k < right; k++) {
dp[left, right] = Math.Max(dp[left, right], numsWithBoundaries[left] * numsWithBoundaries[k] * numsWithBoundaries[right] + dp[left, k] + dp[k, right]);
}
}
}
return dp[0, n + 1];
}
}The C# bottom-up solution constructs a two-dimensional DP array similar to the other implementations. It systematically computes and combines results from subproblems to solve the original problem using iterative dynamic programming.