Leetcode 312 戳气球
题目描述
原文链接： Leetcode 312 戳气球
有 n 个气球，编号为 0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 n u m s [ i − 1 ] ∗ n u m s [ i ] ∗ n u m s [ i + 1 ] nums[i - 1] * nums[i] * nums[i + 1] nums[i−1]∗nums[i]∗nums[i+1]枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。
数据要求
- n == nums.length
- 1 <= n <= 500
- 0 <= nums[i] <= 100
示例
输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =
3
∗
1
∗
5
3*1*5
3∗1∗5 +
3
∗
5
∗
8
3*5*8
3∗5∗8 +
1
∗
3
∗
8
1*3*8
1∗3∗8 +
1
∗
8
∗
1
1*8*1
1∗8∗1 = 167
输入：nums = [1,5]
输出：10
解法
为了方便处理，我们对 nums \textit{nums} nums数组稍作处理，将其两边各加上题目中假设存在的 nums [ − 1 ] \textit{nums}[-1] nums[−1]和 nums [ n ] \textit{nums}[n] nums[n] ，并保存在 val \textit{val} val数组中，即 val [ i ] = nums [ i − 1 ] \textit{val}[i]=\textit{nums}[i-1] val[i]=nums[i−1]，注意：i 的范围是0，1，2，3，…，n。之所以这样处理是为了处理 nums [ − 1 ] \textit{nums}[-1] nums[−1] ，防止下标越界。
下文中的区间均指数组 val \textit{val} val上的区间。
方法1： 记忆化搜索
观察戳气球的操作，发现这会导致两个气球从不相邻变成相邻，使得后续操作难以处理。于是我们倒过来看这些操作，将全过程看作是每次添加一个气球。
我们定义方法 solve \textit{solve} solve，令 solve ( i , j ) \textit{solve}(i,j) solve(i,j) 表示将开区间 ( i , j ) (i,j) (i,j) 内的位置全部填满气球能够得到的最多硬币数。由于是开区间，因此区间两端的气球的编号就是 i i i和 j j j，对应着 val [ i ] \textit{val}[i] val[i] 和 val [ j ] \textit{val}[j] val[j]。
当 i ≥ j − 1 i \geq j-1 i≥j−1时，开区间中没有气球， solve ( i , j ) \textit{solve}(i,j) solve(i,j) 的值为 0；
当 i < j − 1 i < j-1 i<j−1时，我们枚举开区间 ( i , j ) (i,j) (i,j) 内的全部位置 mid \textit{mid} mid，令 mid \textit{mid} mid 为当前区间第一个添加的气球，该操作能得到的硬币数为 val [ i ] × val [ mid ] × v a l [ j ] \textit{val}[i] \times \textit{val}[\textit{mid}] \times val[j] val[i]×val[mid]×val[j]。同时我们递归地计算分割出的两区间对 solve ( i , j ) \textit{solve}(i,j) solve(i,j)的贡献，这三项之和的最大值，即为 solve ( i , j ) \textit{solve}(i,j) solve(i,j) 的值。这样问题就转化为求 solve ( i , mid ) \textit{solve}(i,\textit{mid}) solve(i,mid)和 solve ( mid , j ) \textit{solve}(\textit{mid},j) solve(mid,j)，可以写出方程：
solve
(
i
,
j
)
=
{
max
mid
=
i
+
1
j
−
1
v
a
l
[
i
]
×
val
[
mid
]
×
val
[
j
]
+
solve
(
i
,
mid
)
+
solve
(
mid
,
j
)
,
i
<
j
−
1
0
,
i
≥
j
−
1
\textit{solve}(i,j)= \begin{cases}{} \displaystyle \max_{\textit{mid} = i + 1}^{j - 1}val[i] \times \textit{val}[\textit{mid}] \times \textit{val}[j] + \textit{solve}(i, \textit{mid}) + \textit{solve}(\textit{mid}, j) ,&i < j - 1 \\ 0, & i \geq j - 1 \end{cases}
solve(i,j)=⎩⎨⎧mid=i+1maxj−1val[i]×val[mid]×val[j]+solve(i,mid)+solve(mid,j),0,i<j−1i≥j−1
为了防止重复计算，我们存储
solve
\textit{solve}
solve的结果，使用记忆化搜索的方法优化时间复杂度。代码如下：
package com.webflux.demo;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class MaxCoins {
public static int[][] rec;
public static int[] val;
public static int maxCoins(int[] nums) {
int n = nums.length;
val = new int[n + 2];
for (int i = 1; i <= n; i++) {
val[i] = nums[i - 1];
}
val[0] = val[n + 1] = 1;
rec = new int[n + 2][n + 2];
for (int i = 0; i <= n; i++) {
Arrays.fill(rec[i], -1);
}
return solve(0, n + 1);
}
private static int solve(int left, int right) {
if (left >= right - 1) {
return 0;
}
if (rec[left][right] != -1) {
return rec[left][right];
}
for (int i = left + 1; i < right; i++) {
int sum = val[left] * val[i] * val[right];
sum += solve(left, i) + solve(i, right);
rec[left][right] = Math.max(rec[left][right], sum);
}
return rec[left][right];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] strs = br.readLine().split(",");
int[] nums = Arrays.stream(strs).mapToInt(Integer::parseInt).toArray();
int res = maxCoins(nums);
System.out.println(res);
}
}
复杂度分析
- 时间复杂度： O ( n 3 ) O(n^3) O(n3)，其中 n 是气球数量。区间数为 n 2 n^2 n2 ，区间迭代复杂度为 O ( n ) O(n) O(n)，最终复杂度为 O ( n 2 × n ) = O ( n 3 ) O(n^2 \times n) = O(n^3) O(n2×n)=O(n3)。
- 空间复杂度： O ( n 2 ) O(n^2) O(n2)，其中 n 是气球数量。缓存大小为区间的个数。
方法2：动态规划
按照方法一的思路，我们发现我们可以通过变换计算顺序，从「自顶向下」的记忆化搜索变为「自底向上」的动态规划。
令 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示填满开区间 ( i , j ) (i,j) (i,j)能得到的最多硬币数，那么边界条件是 i ≥ j − 1 i \geq j-1 i≥j−1, 此时有 d p [ i ] [ j ] = 0 dp[i][j]=0 dp[i][j]=0。
可以写出状态转移方程：
d
p
[
i
]
[
j
]
=
{
max
k
=
i
+
1
j
−
1
v
a
l
[
i
]
×
v
a
l
[
k
]
×
v
a
l
[
j
]
+
d
p
[
i
]
[
k
]
+
d
p
[
k
]
[
j
]
,
i
<
j
−
1
0
,
i
≥
j
−
1
dp[i][j]= \begin{cases}{} \displaystyle \max_{k = i + 1}^{j - 1}val[i] \times val[k] \times val[j] + dp[i][k] + dp[k][j] ,&i < j - 1 \\ 0, & i \geq j - 1 \end{cases}
dp[i][j]=⎩⎨⎧k=i+1maxj−1val[i]×val[k]×val[j]+dp[i][k]+dp[k][j],0,i<j−1i≥j−1
最终答案即为
d
p
[
0
]
[
n
+
1
]
dp[0][n+1]
dp[0][n+1]。实现时要注意到动态规划的次序。
代码如下：
Python代码
#!/usr/bin/env python
# -*- coding:utf-8 -*-
# @FileName :MaxCoins.py
# @Time :2021/4/9 11:44
# @Author :Billy
# @Description Leetcode 312 戳气球 Hard
from typing import List
class Solution:
def maxCoins(self, nums: List[int]) -> int:
n = len(nums)
rec = [[0] * (n + 2) for _ in range(n + 2)]
val = [1] + nums + [1]
for i in range(n - 1, -1, -1):
for j in range(i + 2, n + 2):
for k in range(i + 1, j):
total = val[i] * val[k] * val[j]
total += rec[i][k] + rec[k][j]
rec[i][j] = max(rec[i][j], total)
return rec[0][n + 1]
if __name__ == "__main__":
line = list(map(int, input().split(",")))
sol = Solution()
res = sol.maxCoins(line)
print(res)
Java方法：
/**
* 动态规划方法
*
* @param nums
* @return
*/
public static int maxCoins2(int[] nums) {
int n = nums.length;
int[][] rec = new int[n + 2][n + 2];
int[] val = new int[n + 2];
val[0] = val[n + 1] = 1;
for (int i = 1; i <= n; i++) {
val[i] = nums[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 2; j <= n + 1; j++) {
for (int k = i + 1; k < j; k++) {
int sum = val[i] * val[k] * val[j];
sum += rec[i][k] + rec[k][j];
rec[i][j] = Math.max(rec[i][j], sum);
}
}
}
return rec[0][n + 1];
}