Q51 Burst Balloons - LeetCode 312

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;
    }
}