LeetCode312-Burst Balloons(dp)

时间 2021-01-14

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];
    }
}