# 0312. Burst Balloons
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/burst-balloons/
## 思路
## Code

class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] arr = new int[n+2];
        arr[0]=1; 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 len=1; len<=n; len++){
            for(int i=1; i+len-1<=n; i++){
                int j = i+len-1;
                for(int k=i; k<=j; k++){
                    dp[i][j] = Math.max(dp[i][j], dp[i][k-1]+dp[k+1][j]+arr[i-1]*arr[j+1]*arr[k]);
                }
            }
        }
        return dp[1][n];
    }
}