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.
1public class Solution {
2 public int MaxCoins(int[] nums) {
3 int n = nums.Length;
4 int[] numsWithBoundaries = new int[n + 2];
5 System.Array.Copy(nums, 0, numsWithBoundaries, 1, n);
6 numsWithBoundaries[0] = numsWithBoundaries[n + 1] = 1;
7
8 int[,] memo = new int[n + 2, n + 2];
9
10 return DP(0, n + 1, numsWithBoundaries, memo);
11 }
12
13 private int DP(int left, int right, int[] nums, int[,] memo) {
14 if (left + 1 == right) return 0;
15 if (memo[left, right] > 0) return memo[left, right];
16 int ans = 0;
17 for (int i = left + 1; i < right; i++) {
18 ans = Math.Max(ans, nums[left] * nums[i] * nums[right] + DP(left, i, nums, memo) + DP(i, right, nums, memo));
19 }
20 memo[left, right] = ans;
21 return ans;
22 }
23}C# implementation uses a similar logic pattern. A 2D array is used for memoization, and an auxiliary array is prepared with boundaries. The recursive function DP performs the calculations.
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)
1#include <vector>
#include <algorithm>
int maxCoins(std::vector<int>& nums) {
int n = nums.size();
nums.insert(nums.begin(), 1);
nums.push_back(1);
std::vector<std::vector<int>> dp(n + 2, std::vector<int>(n + 2, 0));
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] = std::max(dp[left][right], nums[left] * nums[k] * nums[right] + dp[left][k] + dp[k][right]);
}
}
}
return dp[0][n + 1];
}In C++, the solution constructs a DP table where the loops iterate over possible subarray lengths and positions. The solution aggregates results with dynamic programming, avoiding the overhead of recursion.