DP problem | bursting balloons

help
,
1

Given the problem:
Given n balloons, indexed from 0 to n-1 . Each balloon is painted with a number on it represented by array nums . You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i . After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

  • You may imagine nums[-1] = nums[n] = 1 . They are not real therefore you can not burst them.
  • 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

I came up with following dp top down memoization solution but its giving TLE(Although its correct). I am not able to find out that is it really dp solution that i have implemented or I am just doing it naively and then memoization.

Can you please help me on this, whether this is really dp i have implemented or not. (I do know the solution which is given in discussion tab, but why this will not work)
Mine Solution:

class Solution {

HashMap<String, Integer> hm;

public int maxCoins(int[] nums) {
    
    int n = nums.length;
    hm = new HashMap<>();
    int ans = solve(nums, 0,n-1,1,1);
    return ans;
}

public int solve(int[] nums, int i, int j, int x, int y){
    
    int n = nums.length;
    if(i>j){
        return 0;
    }
    if(i==j){
        return nums[i]*x*y;
    }
    
    String key = i+" "+j+" "+x+" "+y;
    if(hm.containsKey(key)){
        // System.out.println("hit");
        return hm.get(key);
    }
        
    
    int ans = -1;
    
    // for(int k=i;k<=j;k++){
        
       
    
        for(int m=i+1;m<=j+1;m++){
            
            if(m==j+1){
                int burst = x*nums[i]*y;
                int left = solve(nums,i+1,m-1,nums[i],y);
                ans = Math.max(ans, burst+left);
                break;
            }
                
            int burst = x*nums[i]*nums[m];
            int left = solve(nums,i+1,m-1,nums[i],nums[m]);
            int right = solve(nums,m,j,x,y);
            
            ans = Math.max(ans, burst+left+right);
            
        }        
        
        // }
        
    
    // System.out.println("i:"+i+" j:"+j+" "+ans);
    hm.put(key, ans);
    return ans;
}


}

Problem Link:

2 
#define ll long long
ll dp[505][505];
ll solve(vector<int>& ar,ll i,ll j)
{
    if(i == j)
        return 0;
    if(dp[i][j] != -1)
        return dp[i][j];
    ll ans = 0;
    for(int k=i;k<j;k++)
    {
        ans = max(ans,solve(ar,i,k)+solve(ar,k+1,j)+ar[i-1]*ar[k]*ar[j]);
    }
    return dp[i][j] = ans;
}
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        nums.insert(nums.begin(), 1);
        nums.insert(nums.end(), 1);
        memset(dp,-1,sizeof(dp));
        return solve(nums,1,nums.size()-1);
    }
};

This is a dynamic programming based solution of burst balloon. This problem is variation of standard matrix chain multiplication problem. If you don’t know about matrix chain multiplication you can read it from here. Matrix Chain Multiplication | DP-8 - GeeksforGeeks

3

Thanks for the fast response. I know its variation of matrix chain multiplication. Here, in the code given, you are building the dp state in reverse order. That means, if kth balloon burst in the last, what will be max answer, Like that right. But in my approach, I am solving it what if ith balloon burst rightaway, what will be the answer , then if ith balloon burst after some m-i balloon (see the implementation). So, my question is what is the difference that mine solution is gives TLE?