本题用记忆化搜索或者动态规划
零、闲聊
找完工作有一个多月了，一直在咸鱼。11月了，不能再继续这样了。编程题还要继续刷，感觉一段时间不写，思维确实没有之前灵活了。所以以后还是不断刷题，不断学习。
一、题目
有 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
示例:
输入: [3,1,5,8]
输出: 167
解释: nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 315 + 358 + 138 + 181 = 167
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/burst-balloons
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、分析
2.1 题目分析
这道题是很典型的动态规划题。对于这类题，我也是一直没有太多思路。看了一下大神的讲解，感觉明白了一些。
那这篇博客中我们就从最基础的深度优先遍历，到记忆化搜索，最后到动态规划。三种方法来解决这道题。
2.2 深度优先搜索
题目中气球顺序放置，每次扎破一个气球。那么我们在程序中可以使用链表表示气球，每次扎破一个气球，就从链表中删除一个结点。使用深度优先搜索+回溯遍历所有可能的情况。这样肯定可以找到最优解，但是时间复杂度是n！，数据量大的时候肯定会超时的。
代码如下
//方法一：深度优先搜索，使用链表存储气球，然后
public int maxCoins(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
List<Integer> src = new LinkedList<Integer>(); //链表保存气球
src.add(1);
for (int i = 0; i < nums.length; i++) {
src.add(nums[i]);
}
src.add(1);
return loop(src);
}
private int loop(List<Integer> src) {
if (src.size() <= 2) { //递归的终止条件
return 0;
}
int res = 0;
for (int i = 1; i < src.size() - 1; i++) { //遍历当前每一个结点
int cur = src.get(i);
int temp = src.get(i - 1) * cur * src.get(i + 1); //计算戳爆该结点得到的硬币数量
src.remove(i); //删除该结点
res = Math.max(res, temp + loop(src)); //递归剩下的气球，求出剩下的气球能得到的最大硬币数量
src.add(i, cur); //回溯，添加上该结点
}
return res;
}
深度优先搜索可以找到最优解，但是时间复杂度是n!，是因为重复计算了某些子问题。比如，对于[3, 1, 5, 8]这个气球序列，如果我们用深度优先搜索来解，将[5, 8]这个子问题重复计算了两次。
重复计算了[5, 8]子问题两次
2.3 记忆化搜索
简单的深度优先搜索重复计算了子问题，那么我们可以使用数组将子问题的结果保存下来。
但是在划分子问题的时候有个小技巧
比如对于[3, 1, 5, 8]，可以先戳爆[1]，然后剩下[3]， [5, 8]两个子问题。但是这有问题的，[3]和[5, 8]不是两个独立的子问题，他们相互关联的，因为戳爆一个气球，剩下的气球又连在一起了，3右边的气球应该是5。
这时候我们反向思维，对于[3, 1, 5, 8]，我们可以最后戳爆[1]，这样[3] 和 [5, 8]两个子问题之间就没有关联了。这里比较饶，大家可以看一下这个视频，讲的很好。
这时候我们可以写出状态转移方程
for (int k = start; k <= end; k++) {
res = max(res, helper(start, k - 1) + src[start - 1] * src[k] * src[end + 1] + helper(k + 1, end));
}
并且把每一个子问题的解都保存到dp中。
下面看代码
//方法二 记忆化搜索
List<Integer> src = null; //保存气球的数组
int[][] dp = null; //dp数组
int len = 0;
public int maxCoins(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
len = nums.length;
dp = new int[len + 2][len + 2];
src = new ArrayList<Integer>();
src.add(1);
for (int i : nums) {
src.add(i);
}
src.add(1);
return loop(1, len);
}
private int loop(int start, int end) {
if (start > end) {
return 0;
}
if (dp[start][end] > 0) { //如果有缓存的解，直接返回
return dp[start][end];
}
int res = 0;
for (int k = start; k <= end; k++) { //搜索最优解
//由于我们假设第k个气球是最后戳破的，所有戳破他的时候他的左边和右边的气球分别是start - 1和end + 1
res = Math.max(res, src.get(start - 1) * src.get(k) * src.get(end + 1) + loop(start, k - 1) + loop(k + 1, end));
}
dp[start][end] = res; //将结果保存到数组中
return res;
}
2.4 动态规划
记忆化搜索将子问题的解缓存到数组中，当递归到相同的子问题时，从缓存中读取，相当于进行深度优先搜索时进行减枝。还是自顶向下的顺序进行搜索，只不过递归到某些已经计算过的子问题时不用重复计算了。
我们可以自底向上进行计算，先把最基础的子问题计算完成，然后逐层网上计算，最后计算出来结果。
比如我们先计算长度为1的气球序列的解，然后计算长度为2的气球序列的解，逐层往上。
代码如下
//动态规划
public int maxCoins(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
List<Integer> list = new ArrayList<Integer>();
list.add(1);
for (int i : nums) {
list.add(i);
}
list.add(1);
int dp[][] = new int[n + 2][n + 2];
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] = Math.max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + list.get(i - 1) * list.get(k) * list.get(j + 1));
}
}
}
return dp[1][n];
}
网友评论