Bust Balloons

Burst Balloons
Refer this for intuition

Memoization

class Solution {
    public int maxCoins(int[] nums) {
        int arr[]  = new int[nums.length+2];
        int dp[][] = new int[arr.length][arr.length];
        for(int d[] : dp)Arrays.fill(d,-1);
        arr[0] = 1;
        arr[arr.length-1] = 1;
        for(int i =1;i<arr.length-1;i++){
            arr[i] = nums[i-1];
        }
        return find(1,nums.length,arr, dp);
    }
    public int find(int i ,int j , int nums[], int [][] dp){
        ///base case
        if(i>j) return 0;
        if(dp[i][j]!=-1) return dp[i][j];
        int cost = Integer.MIN_VALUE;
        for(int index = i;index<=j;index++){
            cost = Math.max(cost, nums[i-1]*nums[index]* nums[j+1] + find(i,index-1,nums,dp) + find(index+1,j, nums,dp));
        }
        return dp[i][j]= cost;
    }
}

Tabulation

class Solution {
    public int maxCoins(int[] nums) {
        int arr[]  = new int[nums.length+2];
        arr[0] = 1;
        arr[arr.length-1] = 1;
        for(int i =1;i<arr.length-1;i++){
            arr[i] = nums[i-1];
        }

        int dp[][] = new int[arr.length][arr.length];

        for(int i = nums.length;i>=1;i--){
            for(int j = 1;j<=nums.length;j++){
                if(i>j) continue;
                int cost = Integer.MIN_VALUE;
                for(int index = i;index<=j;index++){
                cost = Math.max(cost, arr[i-1]*arr[index]* arr[j+1] + dp[i][index-1] + dp[index+1][j]);
                }
                dp[i][j]= cost;
            }
        }

        return dp[1][nums.length];
    }
}