戳气球
问题描述：
有 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 = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/burst-balloons
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解决方案
该问题就属于动态规划中的难题了，属于区间动态规划类型。
若使用dfs+回溯依次选择一个气球扎破，枚举出所有可能的情况，很明显就是一个全排列问题，但是其复杂度为O（n!）,n=500肯定是过不了的。
该问题需要换一种思路，从后往前算，对于该问题的解（一组扎气球的顺序）从后往前算和从前往后算值总是相同的，因此扎气球问题可以转化为吹气球问题，每次吹一个气球放到数组中，并且获得硬币。
为了易于编码对给定数组两端添加一个1。
dfs+记忆集
定义process(i, j)为填满i, j范围(其中不包括i, j)可以获得的最大硬币数目。
代码如下：
class Solution {
public int maxCoins(int[] nums) {
int N = nums.length;
int[] val = new int[N + 2];
for(int i = 1; i <= N; i++){
val[i] = nums[i - 1];
}
val[0] = 1;
val[N + 1] = 1;
int[][] dp = new int[N + 2][N + 2];// 记忆集
for(int i = 0; i < dp.length; i++){
Arrays.fill(dp[i], -1);// 用-1标记未访问
}
return process(0, N + 1, dp, val);
}
// 返回将（i,j）填满能够获得的最大硬币数
public int process(int i, int j, int[][] dp, int[] val){
if(i >= j - 1){
return 0;
}
if(dp[i][j] != -1){
return dp[i][j];// 已经访问过了
}
int ans = 0;
for(int k = i + 1; k < j; k++){
ans = Math.max(ans, val[i] * val[j] * val[k] +
process(i, k, dp, val) + process(k, j, dp, val));
}
dp[i][j] = ans;
return ans;
}
}相当于对记忆集每个位置计算一次，每次计算的时间复杂度为O(N),因此总体时间复杂度为O(N ^ 3)。额外空间复杂度为O（N^2）
动态规划
这问题该动态规划的时间复杂度同dfs+递归相同，只是各个点的计算顺序不同罢了。
定义dp[i] [j]为填满i, j范围(其中不包括i, j)可以获得的最大硬币数目。
转移方程：
代码如下：
class Solution {
public int maxCoins(int[] nums) {
int N = nums.length;
int[] val = new int[N + 2];
for(int i = 1; i <= N; i++){
val[i] = nums[i - 1];
}
val[0] = 1;
val[N + 1] = 1;
int[][] dp = new int[N + 2][N + 2];
for(int i = N + 1; i >= 0; i--){
for(int j = i + 2; j < N + 2; j++){
for(int k = i + 1; k <= j - 1; k++){
dp[i][j] = Math.max(dp[i][j], val[i] * val[j] * val[k] + dp[i][k] + dp[k][j]);
}
}
}
return dp[0][N + 1];
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-07-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录