LeetCode 312. Poke balloon daily

Problem description

Yes n A balloon , The number is 0 To n - 1, Each balloon is marked with a number , There are arrays of these numbers  nums  in .

Now I ask you to prick all the balloons . Pierce the second i A balloon , You can get  nums[i - 1] * nums[i] * nums[i + 1] Coin .  there i - 1 and i + 1 For and on behalf of  i  The serial number of the two adjacent balloons . If i - 1 or i + 1 Beyond the bounds of the array , Then think of it as a number for 1 The balloon .

Find the maximum number of coins you can get .

Example 1：
Input ：nums = [3,1,5,8]
Output ：167
explain ：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167
Example 2：

Input ：nums = [1,5]
Output ：10
 

Tips ：

n == nums.length
1 <= n <= 300
0 <= nums[i] <= 100

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/burst-balloons
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Java

class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] arr = new int[n + 2];
        arr[0] = arr[n + 1] = 1;
        for(int i = 0;i < n;i++) arr[i + 1] = nums[i];

        int[][] dp = new int[n + 2][n + 2];

        for(int i = n - 1;i >= 0;i--){
            for(int j = i + 2;j <= n + 1;j++){
                // First find two boundaries i and j, Then poke the balloon between them , Open range 
                for(int k = i + 1;k < j;k++){
                    // Number i To number j The maximum score is ： Number i To number k Score of + Number k To number j Score of + The stamp number is k Score of 
                    dp[i][j] = Math.max(
                        dp[i][j],
                        dp[i][k] + dp[k][j] + arr[i] * arr[k] * arr[j]
                    );
                }
            }
        }
        // The number is 1 To No n The balloon with the highest score 
        return dp[0][n + 1];
    }
}