Q25 Burst Balloons - LeetCode 312
Thu Apr 06 2023 10:49:52 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public int maxCoins(int[] nums) {
//this is a question of matrix chain multiplication dp playlist vid23
//adding an extra 1 in the end of the array
int n = nums.length;
int dp[][] = new int[n][n];
for(int gap = 0; gap < n ; gap++){
for(int i = 0 , j = gap ; j < n ; i++ , j++){
int max = Integer.MIN_VALUE;
for(int k = i ; k <= j ;k++){
int left = k==i ? 0: dp[i][k-1] ;
int right = k==j ? 0: dp[k+1][j] ;
//cost = nums[i-1] * nums[k] * nums[j+1]
//handling for i==0 and j == n-1
int cost = nums[k];
cost *= i > 0 ? nums[i-1] : 1;
cost *= j != n-1 ? nums[j+1] :1;
max = Math.max(max , left + right + cost);
}
dp[i][j] = max;
}
}
return dp[0][n-1];
}
}
content_copyCOPY
https://leetcode.com/problems/burst-balloons/
Comments