If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.
It seems a DP problem.
3*4*5; 3*5*6;
Let me assume a X,Y; then the result will be 1*X*Y + 1*Y*1 and X*Y*1 + 1*X*1
Can we use DP???
Yes...the answer is the standard DP solution.
dp[i][j] represent the maximum value of i-j; then how can we infer the value of i,j? dp[i][j] must has a balloon broken finally. We assume this balloon is k; then we can know dp[i][j] = max(dp[i][j],b[k]*b[i-1]*b[j+1] + dp[i][k-1] + dp[k+1][j])
so, if we want to know i,j we must know the i,k; k,j;
so for example, we want to know 1,n; we must have knew the 1,k; k,n;
so the order of our dp transfermation is [3] -> [1] -> [5] -> [8] -> [3, 1] -> [1, 5] -> [5, 8] -> [3, 1, 5] -> [1, 5, 8] -> [3, 1, 5, 8]
therefore, we need to enumerate length first. Then enumerate start place. Then enumerate the middle place.
Amazing!