力扣解题思路：312. 戳气球_力扣戳气球

这题比较巧妙地就是动态规划的方法，以两个数作为左右端点，找出最优解中它们中间那个戳破的气球，中间这个气球把整个队列分为了2部分，要想让中间这个气球和2个端点靠在一起，就需要先把分开的2部分的气球戳破。 dp[i][j]表示i~j最大值，i，j不戳破。 比如k气球在i,j之间时(i,k,j)被戳破，那么要先戳破i,k、k,j之间(i+1~k-1,k+1~j-1)的气球(这里一定要注意的是，最后戳破的才是k)。

所以dp[i][j]=dp[i][k]+dp[k][j]+nums[i]*nums[k]*nums[j]
(因此这里不是nums[k-1]*nums[k]*nums[k+1])

public int maxCoins(int[] nums) {
   
    int n = nums.length;
    int[][] dp = new int[n+2][n+2];
    int[] nums2 = new int[n+2];
    nums2[0]=1;
    nums2[n+1]=1;
    for(int i=1;i<n+1;i++){
   
        nums2[i] = nums[i-1];
    }
    //dp[i][j] = max(dp[i][k-1]+dp[k+1][j]+nums2[i-1]*nums2[j+1]*nums[k])
    for(int i=1;i<n+1;i++){
   
        dp[i][i] = nums2[i-1]*nums2[i]*nums2
1
2
3
4
5
6
7
8
9
10
11
12
13
14