burst Balloons 戳气球
Given n balloons(气球), indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums.
You are asked to burst（戳破） all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent（相邻的） indices（序号） of i. After the burst, the left and right then becomes adjacent.
Find the maximum coins you can collect by bursting the balloons wisely.
Note:
- You may imagine（假设） nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
Example:
Input: [3,1,5,8]
Output: 167
Explanation（解释）: 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
Analysis
- 数组问题
- 最优解问题
Solutions
DP: 贪心（Greed）
- 每一次选择可获取的最大金币为准
- 遍历n遍
- 代码
// java
class Solution {
public int maxCoins1(int[] nums) {
// 边界判断
if (nums.length == 0) return 0;
// 进行每一轮的择优
int sum = 0;
for (int i = 0;i < nums.length;i++) {
int mini = -1;
for (int j = 1;j < nums.length - 1;j++) {
if (nums[j] == -1) { continue;}
if (mini == -1) {mini = j;continue;}
mini = nums[j] > nums[mini] ? mini : j;
}
if (mini == -1) {continue;}
// 向左找边界
int l = mini - 1,left;
while(l > 0 && nums[l] == -1) {
l--;
}
if (l <= 0) {
left = nums[0];
} else{
left = nums[l];
}
// 向右找边界
int r = mini + 1,right;
while(r < nums.length - 1 && nums[r] == -1) {
r++;
}
if (r >= nums.length - 1) {
right = nums[nums.length - 1];
} else{
right = nums[r];
}
sum += left*nums[mini]*right;
System.out.print("left: "+ left);
System.out.print(", nums[j]: "+ nums[mini]);
System.out.println(", right: "+ right);
nums[mini] = -1;
}
sum += nums[0] * nums[nums.length - 1];
// 处理边界值
if(nums[0] > nums [nums.length - 1]) {
sum += nums[0];
}else {
sum += nums[nums.length - 1];
}
return sum;
}
}
记忆化二分递归
- 代码
// java
class Solution {
public int macCoins(int[] nums) {
if (nums == null || nums.length == 0) {return 0;}
// 添加虚拟边界
int length = nums.length;
int[] nums2 = new int[length + 2];
System.arraycopy(nums,0,nums2,1,length);
nums2[0] = 1;
nums2[length + 1] = 1;
length = nums2.length;
// 存储已经计算好的值，cache[i][j] 表示从i到j内的最大的可获得的硬币数量
int[][] cache = new int[length][length];
return maxCoinsCore(nums,length,0,length - 1,cache);
}
private int maxCoinsCore(int[] nums, int length,int begin,int end,int[][] cache) {
// 回归条件，问题分解到最小子问题
if (begin == end - 1) {
return 0;
}
// 利用缓存，避免重复计算
if (cache[begin][end] != 0) {
return cache[begin][end];
}
// 维护一个最大值
int max = 0;
// 递归更新最大值
for (int i = begin + 1; i < end; i++) {
int temp = maxCoinsCorn(nums,length,begin,i,cache) +
maxCoinsCore(nums,length,i,end,cache) + nums[begin] * nums[i]*nums[end];
if (temp > max) {
max = temp;
}
}
// 缓存已经获得的结果
cache[begin][end] = max;
return max;
}
}
DP 动归
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。对于分治法求解的问题，子问题的相互独立仅仅是同层级的子问题间没有互相依赖。但对于动态规划而言，同层级的子问题可能会依赖相同的低层级问题，这就导致低层级问题可能会被计算多次。
最优子结构
- 如果一个问题的最优解包含其子问题的最优解，我们就称此问题具有最优子结构
- 一个问题具有最优子结构，可能使用动态规划方法，也可能使用贪心方法。所以最优子结构只是一个线索，不是看到有最优子结构就一定是用动态规划求解
重叠子问题
- 子问题空间必须足够“小”，即在不断的递归过程中，是在反复求解大量相同的子问题，而不是每次递归时都产生新的子问题。
- 一般的，不同子问题的总数是输入规模的多项式函数为好
- 如果递归算法反复求解相同的子问题，我们就称最优化问题具有重叠子问题性质
对于前面的分治解法，我们的计算过程分为两个阶段：
- 递归的不断的分解问题，直到问题不可继续分解。
- 当问题不可继续分解，也就是分解到最小子问题后，由最小子问题的解逐步向上回归，逐层求出上层问题的解。
阶段1我们称为递归过程，而阶段2我们称为递归调用的回归过程。我们要做的，就是省略递归分解子问题的过程，将阶段2用递推实现出来。
举个例子，对于区间 0 到 4 之间的结果，递归过程是：
dp[0][4] =max { dp[0][1]+dp[1][4]+nums[0]*nums[1]*nums[4] , dp[0][2]+dp[2][4]+nums[0]*nums[2]*nums[4] , dp[0][3]+dp[3][4]+nums[0]*nums[3]*nums[4] }
标红部分没有达到回归条件，会继续向下分解，以 dp[1][4] 为例：
dp[1][4]= max { dp[1][2]+dp[2][4]+nums[1]*nums[2]*nums[4] , dp[1][3]+dp[3][4]+nums[1]*nums[3]*nums[4] }
标红部分继续分解：
dp[2][4]= dp[2][3] + dp[3][4] + nums[2]*nums[3]*nums[4]
dp[1][3] = dp[1][2] + dp[1][3] + nums[1]*nums[2]*nums[3]
到这里因为已经分解到了最小子问题，最小子问题会带着它们的解向上回归，也就是说我们的回归过程是：dp[3][4] , dp[2][3] , dp[2][4] , dp[1][2] , dp[1][3] , dp[1][4] , dp[0][1] , dp[0][2] , dp[0][3] , dp[0][4] 。
因为 dp[i][j] 依赖的是 dp[i][k] 与 dp[k][j] 其中 i < k < j ，也就是说如果要求解 dp[ i ][ j ] 依赖了 [ i ][ 0 ] 到 [ i ][ j-1 ] 以及 [ i+1 ][ j ] 到 [ j-1 ][ j ] 的值。那么我们在dp表中 i 从 length 递减到 0， j 从 i+1 递增到 j 推演即可。
如果觉着顺序抽象，可以在上述分治解法的基础上，打印出缓存数组的演变过程，来理解回归的计算顺序。
作者：niu-you-rou
链接：https://leetcode-cn.com/problems/burst-balloons/solution/chao-xiang-xi-hui-su-dao-fen-zhi-dao-dp-by-niu-you/
- 代码
// java
class Solution {
public int maxCoins(int[] nums) {
// 避免空指针异常
if(nums == null || nums.length == 0) {
return 0;
}
// 构建新的数组，并创建虚拟边界
int len = nums.length;
int[] nums2 = new int[len + 2];
System.arraycopy(nums,0,nums2,1,length);
nums2[0] = 1;
nums2[len + 1] = 1;
// 创建dp表
len += 2;
int[][] dp = new dp[len][len];
// 开始dp: i 为begin , j 为 end,k 为在i,j区间划分子问题的边界
for (int i = len - 2;i > -1;i--) {
for (int j = i + 2;j < len;j++) {
// 维护一个最大值，如果i,j相邻，值为0
int max = 0;
// 求i~j区间最大值
for (int k = i+1;k < j;k++) {
int temp = dp[i][k] + dp[k][j] + nums2[i] * nums2[k] * nums2[j];
if (temp > max) {
max = temp;
}
}
dp[i][j] = max;
}
}
// 返回最后的结果
return dp[0][len - 1];
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
