LeetCode 312. 戳气球

骑猪看日落 2022-10-29 05:17 168阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]

//解法一：dp 左开右开区间写法
    class Solution {
        
        public int maxCoins(int[] nums) {
        
            int n = nums.length;
            int[] arr = new int[n + 2];
            arr[0] = arr[n + 1] = 1;
            for(int i = 1; i <= n; i++)
                arr[i] = nums[i - 1];
            int[][] dp = new int[n + 2][n + 2];
            for(int len = 1; len <= n + 2; len++){
        
                for(int l = 0; l + len - 1 <= n + 1; l++){
        
                    int r = l + len - 1;
                    for(int k = l + 1; k < r ; k++){
        
                        dp[l][r] = Math.max(dp[l][r], dp[l][k] + dp[k][r] + arr[l] * arr[k] * arr[r]);
                    }
                }
            }
            return dp[0][n + 1];
        }
    }

//解法二：左闭右闭区间写法
    class Solution {
        
        public int maxCoins(int[] nums) {
        
            int n = nums.length;
            int[] arr = new int[n + 2];
            arr[0] = arr[n + 1] = 1;
            for(int i = 1; i <= n; i++)
                arr[i] = nums[i - 1];
            int[][] dp = new int[n + 1][n + 1];
            for(int len = 1; len <= n; len++){
        
                for(int l = 1; l + len - 1 <= n; l++){
        
                    int r = l + len - 1;
                    for(int k = l; k <= r ; k++){
        
                        int t = (k - 1 >= l ? dp[l][k - 1] : 0) + (k + 1 <= r ? dp[k + 1][r] : 0) + arr[l - 1] * arr[k] * arr[r + 1];
                        dp[l][r] = Math.max(dp[l][r], t);
                    }
                }
            }
            return dp[1][n];
        }
    }

//解法三：记忆化搜索 左开右开
    class Solution {
        
        int[][] rec;
        int[] val;
        public int maxCoins(int[] nums) {
        
            int n = nums.length;
            val = new int[n + 2];
            for (int i = 1; i <= n; i++) {
        
                val[i] = nums[i - 1];
            }
            val[0] = val[n + 1] = 1;
            rec = new int[n + 2][n + 2];
            for (int i = 0; i <= n + 1; i++) {
        
                Arrays.fill(rec[i], -1);
            }
            return solve(0, n + 1);
        }
    
        public int solve(int l, int r){
        
            if(l >= r - 1)
                return 0;
            if(rec[l][r] != -1)
                return rec[l][r];
            for(int i = l + 1; i < r; i++){
        
                int sum = val[l] * val[i] * val[r];
                sum += solve(l, i) + solve(i, r);
                rec[l][r] = Math.max(rec[l][r], sum);
            }
            return rec[l][r];
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/699a0d9062e34126b97fee03a5621da1.png