2021-10-22

戳气球

动规划方法关键是要找出重复计算的部分还有就是找出状态转移方程。
当从左到右计算需要右边子问题的计算结果的时候，不妨考虑一下从右到左边计算看看是否是自底向上的，如果是就存储起来。

/**
class Solution {
    int []val;
    int [][]rec;
    public int maxCoins(int[] nums) {
        //第一种方法，记忆化搜索。用分治递归的思路。
        int n = nums.length;
        val = new int [n+2];
        rec = new int [n+2][n+2];
        for(int i = 1;i<n+1;++i){
            val[i]=nums[i-1];
        }
        val[0]=val[n+1]=1;

        for(int i =0 ;i<n+2;i++){
            Arrays.fill(rec[i],-1);
        }
        return solve(0,n+1);
    }

    public int solve(int left,int right){
        //表示没有办法插入气球了。
        if(left>=right-1){
            return 0;
        }
        if(rec[left][right]!=-1){
            return rec[left][right];
        }

        int sum =0;
        for(int i = left+1;i<right;++i){
            sum=val[left]*val[i]*val[right];
            sum+=solve(left,i)+solve(i,right);
            rec[left][right]=Math.max(sum,rec[left][right]);
        }
        //这里的记忆化搜索在于当左边的区间比较小的时候，计算过了，有可能在枚举i 又一次划分左区间的时候已经计算过了，所以直接返回。
        return rec[left][right];

    }
} */
class Solution {
    int []val;
    int [][]rec;
    public int maxCoins(int[] nums) {

        int n = nums.length;
        val = new int [n+2];
        rec = new int [n+2][n+2];
        for(int i = 1;i<n+1;++i){
            val[i]=nums[i-1];
        }
        val[0]=val[n+1]=1;

        for(int i =n-1;i>=0;--i){
            for(int j = i+2;j<n+2;j++){
                for(int k = i+1;k<j;k++){
                    int sum = val[i]*val[k]*val[j];
                    sum+=rec[i][k]+rec[k][j];
                    rec[i][j]=Math.max(sum,rec[i][j]);
                }
            }
        }
        return rec[0][n+1];

    }
}