Daily classic

Spring Outlook by Du Fu (Tang dynasty)

The country broken mountains and rivers in the city spring vegetation deep. Feeling flowers splash tears, hate don’t bird startled.

Beacon fire even in March, the letter is worth ten thousand gold. Hoary hair scratch shorter, hun hun hairpin.

describe

You are given n balloons, indexed from 0 to n – 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

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.

Return the maximum coins you can collect by bursting the balloons wisely.

Example 1:

Input: nums = [3,1,5,8] Output: 167 Explanation: ,1,5,8 nums = [3] - > [3,5,8] - > [3] - > [8] - > [] COINS = 3 * 1 * 5 + 3 * 5 * 8 + 1 * 3 * 1 * 8 * 8 + 1 = 167Copy the code

Example 2:

Input: nums = [1,5]
Output: 10
Copy the code

Note:

n == nums.length
1 <= n <= 500
0 <= nums[i] <= 100
Copy the code

parsing

N balloons are given, indexed from 0 to n-1. Each balloon is painted with a number, represented by the array NUMs. All balloons are required to be blown up. If you break the ith balloon, you get nums[i-1] * NUMs [I] * NUMs [I + 1] coins. If I – 1 or I + 1 is outside the range of the array, it is treated as if it had a balloon coated with 1. Pop balloons to return the largest coins that can be collected.

This is a typical dynamic programming problem, which is easy to understand. The key difficulty is that after hitting a balloon, the score of the remaining balloon will change. This process is difficult to understand if we look forward, we can deduce the process backwards. If we define the dynamic array DP[I][j] to represent the maximum score we can get after we burst all the balloons in the closed interval from I to j in nums. For example, nums = [3,1,5,8], the maximum score we can get when beating balloons in the subarray of length 1 is

In the subarray [3] when the last shot was 3 DP[0][0] = 1*3*1 = 3 in the subarray [1] when the last shot was 1 DP[1][1] = 3*1*5 = 15 in the subarray [5] when the last shot was 5 DP[2] = 1*5*8 = 40 In the subarray [8] DP[3][3] = 5*8*1 = 40 when the last shot is at 8Copy the code

The maximum score we can get when we pop balloons in a subarray of length 2 is zero

In the subarray [3,1] when the last shot is at 3, that is,1 first, then 3; DP[0][1] = Max (3*1*5+1*3*5, 1*3*1+1*1*5) = 30 That's when the last shot was 0 and the maximum score is in the subarray [1,5] when the last shot was 1; DP[1][2] = Max (1*5*8+3*1*8, 3*1*5+3*5*8) = 135, the last shot in the index is 2. DP[2][3] = Max (5*8*1+1*5*1, 1*5*8+1*8*1) = 48Copy the code

The maximum score we can get when we pop a balloon in a subarray of length 3 is zero

When the last shot in the subarray [3,1,5] hits 3, it means that [1,5] has been shot and we know that the maximum score we get is 135; If the last shot is fired at 1, it means that [3] and [5] have been fired. We already know that the maximum scores for [3] and [5] are 3 and 40 respectively. DP[0][2] = Max (135+1*3*8, 3+40+1*1*8, 30+1*5*8) = 159. The last shot in the subarray [1,5,8] has the maximum score when the last shot in the subarray [1,5,8] has the maximum score when the last shot in the subarray [5,8] is 1; If the last shot is fired at 5, it means that [3] and [5] have been fired. We already know that the maximum scores for [3] and [5] are 15 and 40 respectively. DP[1][3] = Max (48+3*1*1, 15+40+3*5*1, 135+3*8*1) = 159 That's when the last shot hits index 3Copy the code

The maximum score we can get when we pop balloons in a subarray of length 4 is zero

When the last shot in the subarray [3,1,5,8] is 3, it indicates that [1,5,8] has been shot, and the maximum score is 159; The last shot is 1, indicating that [3] and [5,8] have been played. We know that the maximum scores for [3] and [5,8] are 3 and 48; The last shot is 5, indicating that [3,1] and [8] have been played, and we know that the maximum score for [3,1] and [8] is 30 and 40; The last shot is an 8, which means [3,1,5] is done, We know,1,5 [3] the biggest score of 159, DP [0] [3] = Max (159 + 1 * 3 * 1, 3 + 48 + 1 * 1 * 1, 30 + 40 + 1 * 5 * 1, 159 + 1 * 8 * 1) = 167, That's when the last shot is at index 3Copy the code

The final dynamic programming results are shown in the following table:

0 1 2 3
0 3, 0 30, 0 159, 0 167, 3
1 15, 1 135, 159, 3
2 40, 2 48, 3
3 40, 3

If they want to figure out the order of beating the balloon, we can see from the index of the records in the table above that the reverse order of beating the balloon is 3, 0, 2, 1, so the final index order of beating the balloon is: 1, 2, 0, 3.

The dynamic programming formula is:

for k in range(i,j+1):
	dp[i][j] = max(dp[i][j], dp[i][k-1]+nums[i-1]*nums[k]*nums[j+1]+dp[k+1][j])
Copy the code

answer

class Solution(object):
    def maxCoins(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        N = len(nums)
        nums = [1]+nums+[1]        
        dp = [[0 for _ in range(N+2)] for _ in range(N+2)]        
        for i in range(1,N+1):
            dp[i][i]=nums[i-1]*nums[i]*nums[i+1]  
        for Len in range(2,N+1):
            for i in range(1,N-Len+2):
                left,right = i,i+Len-1
                for k in range(left,right+1):
                    dp[left][right] = max(dp[left][right],dp[left][k-1]+nums[left-1]*nums[k]*nums[right+1]+dp[k+1][right])
                        
        return dp[1][N]
                

        	      
		
Copy the code

The results

Given in the Python online submission for Burst Balloons. Memory Usage: Each node in the Python online list for Burst Balloons.Copy the code

Original link: leetcode.com/problems/bu…

Your support is my biggest motivation