leetcode戳气球问题

戳气球问题，也称为气球戳破问题（Burst Balloons），是一道经典的动态规划问题。

题目描述：

给定一个数组nums，其中nums[i]表示第i个气球的价值。你可以戳破气球i（i从0到n-1），获得nums[left] * nums[i] * nums[right]的价值，其中left和right分别是戳破气球i左侧和右侧的气球的编号。当i被戳破后，left和right就变成相邻的气球。在戳破所有气球之前，你可以任意次地戳破气球。

求最大的价值。

例如，给定数组[3,1,5,8]，可能的戳破顺序为1, 3, 0, 2（即先戳破1号气球，再戳破3号气球，然后戳破0号气球，最后戳破2号气球），最大的价值为167。

解题思路：

采用动态规划的思路，设dp[i][j]表示戳破区间[i,j]内的所有气球能得到的最大价值。假设最后戳破的气球是k，则区间[i,j]可以分为三个部分：[i,k-1]、k、[k+1,j]。则dp[i][j]的状态转移方程为：

dp[i][j] = max(dp[i][k-1] + nums[i-1]*nums[k]*nums[j+1] + dp[k+1][j]), i<=k<=j

其中，nums[i-1]和nums[j+1]表示戳破气球i-1和气球j+1能得到的价值，因为在区间[i,j]外的气球已经被戳破了。

时间复杂度：O(n^3)

参考代码：

class Solution {
public:
int maxCoins(vector<int>& nums) {
int n = nums.size();
nums.insert(nums.begin(), 1);
nums.insert(nums.end(), 1);
vector<vector<int>> dp(n+2, vector<int>(n+2, 0));
for(int len=1; len<=n; len++) {
for(int i=1; i<=n-len+1; i++) {
int j = i+len-1;
for(int k=i; k<=j; k++) {
dp[i][j] = max(dp[i][j], dp[i][k-1] + nums[i-1]*nums[k]*nums[j+1] + dp[k+1][j]);
}
}
}
return dp[1][n];
}
};