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.
1def maxCoins(nums):
2 nums = [1] + nums + [1]
3 memo = {}
4
5 def dp(left, right):
6 if left + 1 == right:
7 return 0
8 if (left, right) in memo:
9 return memo[(left, right)]
10 ans = 0
11 for i in range(left + 1, right):
12 ans = max(ans, nums[left] * nums[i] * nums[right] + dp(left, i) + dp(i, right))
13 memo[(left, right)] = ans
14 return ans
15
16 return dp(0, len(nums) - 1)This Python solution uses a memoized recursive approach. We define the function dp(left, right) to compute the maximum coins that can be obtained from balloons between left and right. The base case is when there are no balloons to burst between left and right. For each possible balloon i to burst, we maximize our coins by considering bursting i last in that subarray and adding the result from recursive calls to the left and right subproblems.
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>
2#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.