class Solution { public int maxCoins(int[] nums) { //this is a question of matrix chain multiplication dp playlist vid23 //assume you have added an extra 1 in the end and begin of the array int n = nums.length; // return solve(nums , 0 ,n-1 , new Integer[n+1][n+1]); //tabuliztion -> n*n*n | sc-> n*n int[][] dp = new int[n+1][n+1]; for(int i = n-1 ;i >= 0 ;i--){ for(int j = 0 ; j < n ; j++){ if(i > j)continue; //base case else{ int max = (int) -1e9; for(int k = i ; k <= j ; k++){ //handle for out of bounds int temp = (i-1 == -1 ? 1 : nums[i-1]) * nums[k] * (j+1 == n ? 1 : nums[j+1]); temp += (k-1 == -1 ? 0 : dp[i][k-1]) + (k+1 == n ? 0 : dp[k+1][j]); max = Math.max(max ,temp); } dp[i][j] = max; } } } return dp[0][n-1]; } //Recursion - exponential Memo-> n^3 | sc - n(stack height) + n^2 (dp array) public int solve(int nums[] , int i , int j , Integer[][] dp){ int n = nums.length; if(i > j) return 0; //base case if no subproblem exist if(dp[i][j] != null) return dp[i][j]; int max = (int) -1e9; for(int k = i ; k <= j ; k++){ //let kth be the last balloon to be burst int temp = (i-1 == -1 ? 1 : nums[i-1]) * nums[k] * (j+1 == n ? 1 : nums[j+1]); //give me max cost to burst right & left set of balloons temp += solve(nums , i,k-1,dp) + solve(nums , k+1 , j , dp); max = Math.max(max ,temp); } return dp[i][j] = max; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter