for this problem, 2-d dp array stores the subarray results from i to j, that's the subproblem

because the subproblem dp[i][j] depends on every subarray of it self, so the updating order should be something like this:

(i can not be smaller than j, we only need the top right half of this grid)

int the code below, each time we reuse the left part and right part, calculate the last burst balloon value as current part, add those three together to update the dp[i][j]

the reverse thinking here is more about how to update the subproblems (although we can't talk about subproblems separately because the updating rule justifies the subproblem), which means in subproblem dp[i][j], if the kth balloon gets bursted last or not

to help others fully understand this algorithm, I rewrite some part intentionally, notice that when k==i, there's no left part, and when k==j, there's no right part

public class Solution {
public int maxCoins(int[] nums) {
if(nums==null || nums.length<1) return 0;
int len = nums.length;
int[][] dp = new int[len][len];
for(int w=0;w<len;w++)//w determines the subarray length for each step
for(int i=0;i+w<len;i++){
int j = i+w;
for(int k=i;k<=j;k++){//k is the last to burst in dp[i][j] subproblem
int leftPart = k==i?0:dp[i][k-1], rightPart = k==j?0:dp[k+1][j];
int left = i<1?1:nums[i-1], right = j+1>=len?1:nums[j+1];
int curPart = left*nums[k]*right;
dp[i][j] = Math.max(dp[i][j],leftPart+curPart+rightPart);
}
}
return dp[0][len-1];
}
}

the k is the essence of this algorithm, from the divide and conquer POV, we use k to cut the problem in two parts(not necessarily half), and for each subproblem, we repeat this procedure.

there maybe two confusion part exist if you do not properly understand the algorithm:

k is the last to burst in the subproblem, but k may not be the last to burst in the whole problem
when doing the calculation of dp[i][j], we left the leftpart as 0 when k==i, left the rightpart as 0 when k==j. So when calculating the value dp[i][i], we left the left part and right part as 0 when k==i, instead of calculating left part and right part as 1 * 1 * 1. Think about the coherence how you will do when the subproblem becomes the whole problem

Runtime: the subproblems updating time complexity is O(n), there're O(n^2)subproblems, total time complexity is O(n^3), space complexity is O(n^2) and it can't not be optimized to O(n) in this case because of the updating order