LeetCode312-Burst Balloons(dp)
LeetCode312-Burst Balloons(dp)
- 递归写法
- 二维dp
题目链接
题目
递归
这题递归本来用ArrayList写了一个，也是枚举删除的位置，递归后插入还原，但是那样不好记忆化，于是看了讨论区。。。答案有点分治的意思。。
思路: (注意这里process函数(递归函数)求的是在[L,R]闭区间可以取的最大值)
- 如果L > R，则区间无数，这是递归边界，返回0；
- 否则，在[L,R]区间内，枚举"删除"每一个数，然后这个数的两边([L,i-1] 和[i+1][R])都需要先递归的求出他们的最大值；
- 然后，最重要的一点: 因为两边是先递归的，所以其实这些数已经被删除了，所以我们枚举[L,R]的时候(用一个变量i枚举)，不能在求的时候写出 arr[i] * arr[i-1] * arr[i+1]，而是arr[i] * arr[L-1] * arr[R+1]；
- 然后我们要注意边界 ，也就是i = 0 和i == arr.length - 1的情况特殊处理一下；
class Solution {
public int maxCoins(int[] nums) {
if(nums == null || nums.length == 0)
return 0;
int[][] map = new int[nums.length][nums.length];
return process(nums,0,nums.length-1,map);
}
private int process(int[] arr,int L,int R,int[][] map){
if(L > R ) //中间没有数了
return 0;
// if(L == R) //注意这里不是习惯性的这样写，因为递归函数只是一个区间而已，并不是真的只剩下一个数了
// return arr[L];
if(map[L][R] != 0)
return map[L][R];
int res = 0;
for(int i = L; i <= R; i++){
int sum = 0;
int center = arr[i];
if(L != 0)
center *= arr[L-1];
if(R != arr.length-1)
center *= arr[R+1];
sum += center;
sum += process(arr,L,i-1,map);
sum += process(arr,i+1,R,map);
res = Math.max(res,sum);
}
map[L][R] = res;
return res;
}
}
另一种写法，使用开区间的写法，有一些不同:
- 先在数组的两边都加上1，这样就不需要处理边界，因为center是相乘，不影响结果；
- 边界就变成了L + 1 == R，因为是开区间(L,R)这种情况就是区间内没有数了，也就是边界；
- 其他的类似；
class Solution {
public int maxCoins(int[] nums) {
if(nums == null || nums.length == 0)
return 0;
int[] newNums = new int[nums.length + 2];
int n = 1;
for(int num : nums)
newNums[n++] = num;
newNums[0] = newNums[n] = 1;
int[][] map = new int[nums.length+2][nums.length+2]; // num.length + 2
return process(newNums,0,newNums.length-1,map); //注意都是newNum 实际求的是 [1,newNums.length-2]
}
private int process(int[] arr,int L,int R,int[][] map){
if(L+1 == R ) //中间没有数了 因为求的是开区间的
return 0;
if(map[L][R] != 0)
return map[L][R];
int res = 0;
for(int i = L+1; i <= R-1; i++){
int sum = 0;
int center = arr[i];
center *= arr[L];
center *= arr[R];
sum += center;
sum += process(arr,L,i,map);
sum += process(arr,i,R,map);
res = Math.max(res,sum);
}
map[L][R] = res;
return res;
}
}
二维dp
仿照第一种写法写出来的动态规划:
这里有一个很重要的地方:
- 就是更新的顺序，这就是为什么这个题目不好写出一维的动态规划的原因。某个位置dp[i][j] 依赖的地方很不是一排的(左边和下面)；
- 图中，棕色的方块是0，因为L > R；
- 然后其他的就和递归差不多了；
class Solution {
public int maxCoins(int[] nums) {
if(nums == null || nums.length == 0)
return 0;
int[][] dp = new int[nums.length][nums.length];
for(int L = nums.length - 1; L >= 0; L--){//注意这里的顺序
for(int R = L; R < nums.length; R++){
int res = 0;
for(int i = L; i <= R; i++){
int sum = 0;
int center = nums[i];
if(L != 0)
center *= nums[L-1];
if(R != nums.length-1)
center *= nums[R+1];
sum += center;
if(L <= i-1)
sum += dp[L][i-1];
if(i+1 <= R)
sum += dp[i+1][R];
res = Math.max(res,sum);
}
dp[L][R] = res;
}
}
return dp[0][nums.length-1];
}
}
同样第二种方法的dp写法，这种写法要自己拷贝一份数组，但是好处是，不要去判断一些繁琐的边界，因为我们的newNum[0] = newNum[newNum.length -1] = 1，这样不要判断越界: 同样也要注意L和R更新的顺序:
class Solution {
public int maxCoins(int[] nums) {
if(nums == null || nums.length == 0)
return 0;
int[] newNums = new int[nums.length + 2];
int n = 1;
for(int num : nums)
newNums[n++] = num;
newNums[0] = newNums[n] = 1;
int[][] dp = new int[nums.length+2][nums.length+2];
for(int L = newNums.length-1; L >= 0; L--){ //同样不能写成for(int L = 0; L < newNums.length; L++)
for(int R = L; R < newNums.length; R++){
int res = 0;
// (L,R) 开区间
for(int i= L + 1; i <= R-1; i++){
int sum = 0;
int center = newNums[i];
center *= newNums[L];
center *= newNums[R];
sum += center;
sum += dp[L][i];
sum += dp[i][R];
res = Math.max(res,sum);
}
dp[L][R] = res;
}
}
return dp[0][newNums.length-1];
}
}