For anyone that is still confused after reading all kinds of explanations...
I think the most upvoted post didn't talk about what dp[i][j] represent and what exactly does the transition function : \n\nfor (int k = left; k <= right; ++k)\
I think the most upvoted post didn't talk about what dp[i][j] represent and what exactly does the transition function : \n\n**for (int k = left; k <= right; ++k)\n                    dp[left][right] = max(dp[left][right], nums[left-1] * nums[k] * nums[right+1] + dp[left][k-1] + dp[k+1][right])****\n means.  \n\nOr maybe it did talk about it but I miss it. But anyway here is my understand of this problem after reading countless of posts and comments : \n\nFirst of all, dp[i][j] in here means, the maximum coins we get after we burst **all** the balloons between i and j in the original array. \n\nFor example with input [3,1,5,8] :\n\ndp[0][0] means we burst ballons between [0,0], which means we only burst the first balloon in original array. So dp[0][0] is 1 * 3 * 1 = 3.\n\ndp[1][1] means we burst balloons between [1][1], which means we only burst the second ballon in the original array. So dp[1][1] is 3 * 1 * 5 = 15.\n\nSo in the end for this problem we want to find out dp[0][ arr.length - 1 ], which is the maximum value we can get when we burst all the balloon between [0 , length -1]\n\nTo get that we need the transition function :\n\n**for (int k = left; k <= right; ++k)\n                    dp[left][right] = max(dp[left][right], nums[left-1] * nums[k] * nums[right+1] + dp[left][k-1] + dp[k+1][right])****\n\nThis transition function basically says in order to get the maximum value we can get for bursting all the balloons between  [ i , j] , we just loop through each balloon between these two indexes and make them to be the last balloon to be burst, \n\nwhy we pick it as the last balloon to burst ?\n\nFor example when calculating dp[0,3] and picking index 2 as the last balloon to burst, \n\n [ 3 , 1 , 5 , 8] ,  that means 5 is the last balloon to burst between [0,3] , to get the maximum value when picking 5 as the last balloon to burst :\n\nmax = maximum value of bursting all the balloon on the left side of 5 + maximum value of bursting all the balloon on the right side of 5 + bursting balloon 5 when left side and right side are gone. \n\nThat is dp[0, 1]  + nums[0 - 1] * nums[2] * nums[3 + 1] + + dp[3,3];  \n \nThat is dp[left, k - 1]  + nums[left - 1] * nums[k] * nums[right + 1] + dp[k+1, right] ; \n\nto get the maximum dp[left, right] we just loop through all the possible value of k to get the maximum.\n\n\nHope it helps!
[]