【dfs && 记忆化搜索&&区间dp】leet-312. 戳气球

有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。示例 1：

示例 2：

输入：nums = [1,5]
输出：10

提示：

• n == nums.length
• 1 <= n <= 300
• 0 <= nums[i] <= 100

在数组前后分别补上1，变成：1，1，5，1

memo[left][right] 表示在 （left,right) 开区间戳破所有气球获取的最大的硬币。很明显：答案=memo[0][n+1]

memo[left][right]= Math.max(memo[left][right], 开区间（left，right）范围内 戳破 第i个气球获取的最大的硬币); 此时i 取值[left+1,right-1]

开区间（left，right）范围内，戳破 第i个气球获取的最大的硬币= memo[left][i] +a[left]*a[i]*a[right] + memo[i][right]

memo[left][i] ：已经戳破开区间（left,i)所有气球获取的最大值，

memo[i][right]：已经戳破开区间(i,right)所有气球获取的最大值，

a[left]*a[i]*a[right]：最后戳破i获取的值

迭代 i 从【left+1，right-1】获取最后戳破每个i能够获取的最大值， memo[left][right]就是这些值的max值

所以答案：

     public int maxCoins(int[] nums) {
        int n=nums.length;
        int[][] dp=new int[n+2][n+2];
        int[] a=new int[n+2];
        System.arraycopy(nums,0,a,1,nums.length);
        a[0]=1;
        a[n+1]=1;
        return dfs(a,0,n+1,new Integer[n+2][n+2]);

    }

    public int dfs(int[] a,int left,int right, Integer[][] memo){
        if(left+1==right) return 0;
        if(memo[left][right]!=null) return memo[left][right];

        int ans=0;
        for(int i=left+1;i<right;i++){ //依此最后戳破i，ans是每个i对应值的最大值
            ans=Math.max(ans,dfs(a,left,i,memo)+a[left]*a[i]*a[right]+dfs(a,i,right,memo));
        }
        memo[left][right]=ans;
        return memo[left][right];
    }

代码转成动态规划：

    public int maxCoins(int[] nums) {
        int n=nums.length;
        int[][] dp=new int[n+2][n+2];
        int[] a=new int[n+2];
        System.arraycopy(nums,0,a,1,nums.length);
        a[0]=1;
        a[n+1]=1;
        System.out.println(Arrays.toString(a));
        for(int r=1;r<n+2;r++){
            for(int l=r-1;l>=0;l--){
                if(l+1==r) dp[l][r]=0;
                else{
                    int ans=0;
                    for(int i=l+1;i<r;i++){
                        ans=Math.max(ans,dp[l][i]+a[l]*a[i]*a[r]+dp[i][r]);
                    }
                    dp[l][r]=ans;
                }
            }
        }
        return dp[0][n+1];

    }