链接
https://leetcode-cn.com/problems/burst-balloons/
耗时
解题：null min
题解：31 min
题意
有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。
求所能获得硬币的最大数量。
说明:
- 你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
- 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
思路
不会，根本没有思路，我只想到了
O
(
n
!
)
O(n!)
O(n!) 的 dfs，所以下面是根据官方解法的理解复述。
戳破气球难以解决（确实，我想了一天），反向思考将问题改为添加气球。为避免越界，先将 nums[0:n-1] 换到 val[1:n] 中，然后赋值 val[0] = val[n+1] = 1。dp[i][j] 表示 i 到 j 的编号区间添加满气球可以获得硬币的最大数量，其中区间 (i,j) 不包含 i，j 本身。
这种思路可以分为两种情况：
-
i
≥
j
−
1
i \geq j-1
i≥j−1，区间中不包含气球，dp[i][j] = 0
-
i
<
j
−
1
i < j-1
i<j−1，(i,j) 区间中每个位置作为第一个添加气球的位置都试一下，那么 k 作为 (i,j) 中第一个添加气球的位置，其可以使得 (i,j) 区间填满气球所能获得硬币的最大数量为
d
p
[
i
]
[
k
]
+
v
a
l
[
i
]
∗
v
a
l
[
k
]
∗
v
a
l
[
j
]
+
d
p
[
k
]
[
j
]
dp[i][k] + val[i] * val[k] * val[j] + dp[k][j]
dp[i][k]+val[i]∗val[k]∗val[j]+dp[k][j]，所以 dp[i][j] = max(
d
p
[
i
]
[
k
]
+
v
a
l
[
i
]
∗
v
a
l
[
k
]
∗
v
a
l
[
j
]
+
d
p
[
k
]
[
j
]
dp[i][k] + val[i] * val[k] * val[j] + dp[k][j]
dp[i][k]+val[i]∗val[k]∗val[j]+dp[k][j])
状态转移方程：
d
p
[
i
]
[
j
]
=
{
max
k
=
i
+
1
j
−
1
(
d
p
[
i
]
[
k
]
+
v
a
l
[
i
]
∗
v
a
l
[
k
]
∗
v
a
l
[
j
]
+
d
p
[
k
]
[
j
]
)
(
i
<
j
−
1
)
0
(
i
≥
j
−
1
)
dp[i][j] = \begin{cases} \max_{k=i+1}^{j-1} (dp[i][k] + val[i] * val[k] * val[j] + dp[k][j]) \ \ (i < j-1)\\ 0 \ \ (i \geq j-1) \end{cases}
dp[i][j]={maxk=i+1j−1(dp[i][k]+val[i]∗val[k]∗val[j]+dp[k][j]) (i<j−1)0 (i≥j−1)
由于需要用到下面计算的结果，所以自底向上 dp。
时间复杂度：
O
(
n
3
)
O(n^3)
O(n3)
AC代码
class Solution {
public:
int maxCoins(vector<int>& nums) {
int n = nums.size();
vector<int> val(n+2);
for(int i = 1; i <= n; ++i)
val[i] = nums[i-1];
val[0] = val[n+1] = 1;
vector<vector<int>> dp(n+2, vector<int>(n+2, 0));
for(int i = n-1; i >= 0; --i) {
for(int j = i+2; j <= n+1; ++j) {
for(int k = i+1; k <= j-1; ++k) {
dp[i][j] = max(dp[i][j], dp[i][k]+val[i]*val[k]*val[j]+dp[k][j]);
}
}
}
return dp[0][n+1];
}
};
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
