312. Burst Balloons
You are given n
balloons, indexed from 0
to n - 1
. Each balloon is painted with a number on it represented by an array nums
. You are asked to burst all the balloons.
If you burst the ith
balloon, you will get nums[i - 1] * nums[i] * nums[i + 1]
coins. If i - 1
or i + 1
goes out of bounds of the array, then treat it as if there is a balloon with a 1
painted on it.
Return the maximum coins you can collect by bursting the balloons wisely.
Example 1:
Input: nums = [3,1,5,8] Output: 167 Explanation: nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> [] coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
Example 2:
Input: nums = [1,5] Output: 10
Constraints:
n == nums.length
1 <= n <= 300
0 <= nums[i] <= 100
Solution:
Let us take the array as [ B1, B2, B3, B4 ] with Bi as the number on the ith balloon. We can add 1 on the left and right as we can go out of bound, so the array now becomes
[ 1, B1, B2, B3, B4, 1 ]
i j
To solve the problem we can take range now as i and j.
Base Condition: while(i<=j)
so here our index goes from i to j and we solve the subproblem while (i<=j). Let's see the function.
fun(i,j){
if(i>j)return 0;
int cost=INT_MIN;
for(ind = i->j){
cost=max(cost,arr[i-1]*arr[ind]*arr[j]+fun(i,ind-1)+fun(ind+1,j);
}
return cost;
}
Time Complexity: Exponential (because of overlapping subproblem)
Memoization:
We will make an array dp[n+1][n+1] and for every state i and j we will store the results of fun(i,j). So the Time Complexity will change to N x N x N = N3
Tabulation:
1. Write Base Case
2. See what is changing i.e opposite of recursion ( i -> n to 1, j -> 1 to n)
3. Copy the recurrence
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.