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.
1#include <vector>
2#include <algorithm>
3
4int maxCoins(std::vector<int>& nums) {
5 int n = nums.size();
6 nums.insert(nums.begin(), 1);
7 nums.push_back(1);
8 std::vector<std::vector<int>> memo(n + 2, std::vector<int>(n + 2, 0));
9
10 auto dp = [&](int left, int right, auto&& dp) -> int {
11 if (left + 1 == right) return 0;
12 if (memo[left][right] > 0) return memo[left][right];
13 int ans = 0;
14 for (int i = left + 1; i < right; ++i) {
15 ans = std::max(ans, nums[left] * nums[i] * nums[right] + dp(left, i, dp) + dp(i, right, dp));
16 }
17 memo[left][right] = ans;
18 return ans;
19 };
20
21 return dp(0, n + 1, dp);
22}In this C++ solution, a lambda function for recursive memoization is used. We append and prepend a 1 to handle boundary conditions and initialize a matrix memo for caching results. The dp lambda defined inside captures the same logic as the Python version describing essentially the same approach.
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
Java implementation resembles the Python approach in using a double loop structure to build the solution iteratively. It fills up the DP table as results for progressively larger sections of the array get combined.