Leetcode 312

Leetcode 312

题意

给了一个数组n，代表n个气球，每个气球有一个值 ai $a_i$，现在，你每次可以扎破一个气球 ai $ai$，得到的收益为 ai∗ai−1∗ai+1 $a_i*a_{i - 1}*a_{i +1}$。最边上的 ai−1 $a_{i - 1}$或 ai+1 $a_{i+1}$即为1，求我们扎破所有气球得到的最大收益。

思路

明显的一个区间dp。

状态表示： d[i][j] $d[i][j]$，区间[i, j]的最大收益。

然后我们需要考虑的就是如何定义我们的子问题了，最先考虑的是在区间[i, j]内首先扎破气球k，得到的最大收益，我们很快就会发现这样一个问题：我们扎破k之后，k - 1和k + 1变得相邻，会影响我们 d[i,k−1] $d[i, k - 1]$和 d[k+1,j] $d[k + 1, j]$的计算，即存在后效性问题。

然后这道题存在一个非常巧妙的解法，也是在dp中非常常见的想法，我们反过来考虑，我们设k为区间[i, j]内最后一个扎破的气球( i<k<j $i < k < j$)：首先，扎破k的收益为： ak∗ai∗aj $a_k*a_i*a_j$（因为此时区间内只剩下 ai $a_i$， ak $a_k$， aj $a_j$）。然后，我们再来考虑有没有后效性问题，因为k是最后一个扎破的，那么子问题就变成了上一次扎破的两个区间： d[i,k] $d[i, k]$和 d[k,j] $d[k, j]$。并且，这两个区间没有任何约束关系，是相互独立的。

因此，我们可以得到我们的转移方程：
d[i][j]=max(d[i][j],d[i,k]+d[k,j]+ai∗ak∗aj)i<k<j $d[i][j] = max(d[i][j], d[i, k] + d[k, j] + a_i*a_k*a_j) quad i < k < j$

边界情况： d[i][j]=0j==i+1 $d[i][j] = 0 quad j == i + 1$

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

空间复杂度： O(n2) $O(n^2)$。

代码

const int maxn = 505;
int d[maxn][maxn];class Solution {
public:int dfs(int i, int j, vector<int>& nums) {if (j == i + 1) return d[i][j] = 0;if (d[i][j] >= 0) return d[i][j];for (int k = i + 1; k < j; k++) {d[i][j] = max(d[i][j], dfs(i, k, nums) + dfs(k, j, nums) + nums[k] * nums[i] * nums[j]);}return d[i][j];}int maxCoins(vector<int>& nums) {memset(d, -1, sizeof(d));vector<int> v;v.push_back(1);for (auto x : nums) v.push_back(x);v.push_back(1);return dfs(0, v.size() - 1, v);}
};