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)
1def
The Python solution uses a bottom-up dynamic programming table to iterate through all subarray lengths from 3 upwards since we initially padded the nums array. This way, we are able to systematically determine the most coins by considering each k element in this sub-array as the last balloon to burst and combining results from smaller subproblems.