leetcode312 戳气球

本文主要是介绍leetcode312 戳气球，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

思路：

逆向思维，一个一个移除气球不好处理，改为一个一个增加气球，就可以使用区间dp计算了。

实现：

 1 class Solution {
 2 public:
 3     int maxCoins(vector<int>& nums) {
 4         int n=nums.size();
 5         vector<int>a(n+2,1);
 6         for(int i=0;i<n;i++){
 7             a[i+1]=nums[i];
 8         }
 9         vector<vector<int>>dp(n+2,vector<int>(n+2,0));
10         for(int i=n+1;i>=0;i--){
11             if(i+2<=n+1)dp[i][i+2]=a[i]*a[i+1]*a[i+2];
12             for(int j=i+3;j<=n+1;j++){
13                 for(int k=i+1;k<j;k++){
14                     dp[i][j]=max(dp[i][j],dp[i][k]+a[k]*a[i]*a[j]+dp[k][j]);
15                 }
16             }
17         }
18         return dp[0][n+1];
19     }
20 };

这篇关于leetcode312 戳气球的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！