蛮难的一道题…
动态规划
class Solution
{
public:int maxCoins(vector<int> &nums){
// 首尾插入1便于计算nums.insert(nums.begin(), 1);nums.push_back(1);int size = nums.size();//dp[i][j]表示戳破(i,j)之间所有气球所取得的最大值vector<vector<int>> dp(size, vector(size + 1, 0));//每次至少有一个气球需要戳破,因此间隔i从2开始取for (int i = 2; i < nums.size(); i++)for (int j = 0; j + i < nums.size(); j++)// 遍历戳破(i,j)之间每个气球k的可能性for (int k = j + 1; k < j + i; k++)dp[j][j + i] = max(dp[j][j + i], dp[j][k] + dp[k][j + i] + nums[j] * nums[k] * nums[j + i]);return dp[0][size - 1];}
};