# Java solution with explanation - 13ms

• If we go the route of choosing a balloon to burst and then write the recurrence relation then we cannot solve it by DP. The reason being after a chosen balloon is burst the input data changes its shape since neighbors change. The key to a DP solution(apart from having optimal subproblems) is non changing input.
So the idea here is to choose a balloon to be burst last. Hence the recurrence relation stays same but instead will focus on choosing a balloon 'k' to be burst last. So for finding the max coins in a range of i - j, we choose all possible values of k(i <= k <= j) and use the intermediary subproblem solutions to find the max coins for [i,j]

``````    public int maxCoins(int[] nums) {
if(nums==null || nums.length==0) return 0;

int[] nums2 = new int[nums.length+2];
nums2[0] = 1;
nums2[nums2.length-1] = 1;
for(int i=1;i<nums2.length-1;i++) {
nums2[i] = nums[i-1];
}
int[][] dp = new int[nums2.length][nums2.length];
dp[0][0] = 0;
dp[nums2.length-1][nums2.length-1] = 0;

for (int i = 1; i < nums2.length - 1; i++) {
for (int j = i; j >= 1; --j) {
for (int k = j; k <= i; k++) {
dp[j][i] = Math.max(dp[j][i],
dp[j][k - 1] + dp[k + 1][i] + (nums2[j - 1] * nums2[k] * nums2[i + 1]));
}
}
}

return dp[1][nums2.length-2];
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.