312-Burst-Balloons

原题链接

0x0 题目详情

有 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

0x1 解题思路

这道题如何按照我们先去戳爆一个气球m,然后更新气球m-1和m+1的新边界,是非常麻烦的,我目前还没有思考出行之有效的方法。

那么我们换一种思路,逆向DP。就跟递归做法一样,我们先找到递归出口。对于dp,我们可以把每一个气球都当作最后一个戳爆。比如我们把气球m当作最后一个来戳爆,那么这时总的分数就是气球m左边的分数加上气球m右边的分数再加上气球m作为最后一个戳爆的分数。

可以看到,气球分数的区间是有界的。如果此时气球m所在分数区间为[left,right],那么气球m作为最后一个戳爆的分数就是nums[left-1]*nums[m]*nums[right+1]。这里求m的分数用到了区间[left,right]之外的数据。

0x2 代码实现

递归版本:

class Solution {
    public int maxCoins(int[] nums) {
        if(nums==null || nums.length==0){
            return 0;
        }
        return recur(nums,0,nums.length-1);

    }

    //左闭右闭区间,返回在这个区间内的最高得分
    private int recur(int[] nums,int left,int right){

        if(left>right){
            return 0;
        }
        if(left==right){
            return (left-1<0?1:nums[left-1])*nums[left]*(right+1>=nums.length?1:nums[right+1]);
        }

        int result=Integer.MIN_VALUE;
        for(int i=left;i<=right;i++){
            result=Math.max(result,(left-1<0?1:nums[left-1])*nums[i]*(right+1>=nums.length?1:nums[right+1])+
            recur(nums,left,i-1)+recur(nums,i+1,right));
        }
        return result;
    }
}

动态规划版本:

class Solution {
    public int maxCoins(int[] nums) {
        if(nums==null || nums.length==0){
            return 0;
        }
        return recur(nums,0,nums.length-1);

    }

    //左闭右闭区间,返回在这个区间内的最高得分
    private int recur(int[] nums,int left,int right){
        if(left==right){
            return nums[left];
        }
        int[][] dp=new int[nums.length][nums.length];
        int length=nums.length;
        dp[0][0]=nums[0]*nums[1];
        dp[length-1][length-1]=nums[length-1]*nums[length-2];
        for(int i=1;i<nums.length-1;i++){
            dp[i][i]=nums[i-1]*nums[i]*nums[i+1];
        }

        for(int j=1;j<length;j++){
            for(int i=j-1;i>-1;i--){
                for(int q=i;q<=j;q++){
                    dp[i][j]=Math.max(dp[i][j],(i-1<0?1:nums[i-1])*nums[q]*(j+1>=length?1:nums[j+1])+
                    (i>q-1?0:dp[i][q-1])+(q+1>j?0:dp[q+1][j]));
                }
            }
        }
        return dp[0][length-1];
    }
}

0x3 课后总结

对于将递归改成动态规划的题目,对于改的过程我们需要注意以下几个问题:

1. 我们要注意递归求解的方向。比如我们拥有二维dp数组。我们需要思考递归的过程在从上到下用这张表还是从左到右?

2. 得出递归使用表的方向后,在动态规划中填充表的顺序是与递归相反的!!!