For anyone that is still confused after reading all kinds of explanations...


  • 1

    I think the most upvoted post didn't talk about what dp[i][j] represent and what exactly does the transition function :

    for (int k = left; k <= right; ++k)
    dp[left][right] = max(dp[left][right], nums[left-1] * nums[k] * nums[right+1] + dp[left][k-1] + dp[k+1][right])
    **
    means.

    Or 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 :

    First 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.

    For example with input [3,1,5,8] :

    dp[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.

    dp[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.

    So 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]

    To get that we need the transition function :

    for (int k = left; k <= right; ++k)
    dp[left][right] = max(dp[left][right], nums[left-1] * nums[k] * nums[right+1] + dp[left][k-1] + dp[k+1][right])
    **

    This 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,

    why we pick it as the last balloon to burst ?

    For example when calculating dp[0,3] and picking index 2 as the last balloon to burst,

    [ 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 :

    max = 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.

    That is dp[0, 1] + nums[0 - 1] * nums[2] * nums[3 + 1] + + dp[3,3];

    That is dp[left, k - 1] + nums[left - 1] * nums[k] * nums[right + 1] + dp[k+1, right] ;

    to get the maximum dp[left, right] we just loop through all the possible value of k to get the maximum.

    Hope it helps!


  • 0

    @jienan2
    Good explanation to the transition function. Thumb up.


Log in to reply
 

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