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.
1import java.util.Arrays;
2
3public class BurstBalloons {
4 public int maxCoins(int[] nums) {
5 int n = nums.length;
6 int[] numsWithBoundaries = new int[n + 2];
7 System.arraycopy(nums, 0, numsWithBoundaries, 1, n);
8 numsWithBoundaries[0] = numsWithBoundaries[n + 1] = 1;
9
10 int[][] memo = new int[n + 2][n + 2];
11
12 return dp(0, n + 1, numsWithBoundaries, memo);
13 }
14
15 private int dp(int left, int right, int[] nums, int[][] memo) {
16 if (left + 1 == right) return 0;
17 if (memo[left][right] > 0) return memo[left][right];
18 int ans = 0;
19 for (int i = left + 1; i < right; i++) {
20 ans = Math.max(ans, nums[left] * nums[i] * nums[right] + dp(left, i, nums, memo) + dp(i, right, nums, memo));
21 }
22 memo[left][right] = ans;
23 return ans;
24 }
25}The Java solution follows the same approach with a recursive function. The array numsWithBoundaries includes extra 1s at each end. The method dp handles the recursive logic with memoization.
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)
1function
JavaScript provides an efficient way to perform similar logic via dynamic programming. The dp table keeps track of intermediate results, iterating across the array and storing max coins for each possible subarray and 'k' position.