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: