312. Burst Balloons

calx 發(fā)布于2019-08-19 10:45 / 2496人閱讀

摘要：接下來就是方程的問題了。首先肯定是要遍歷切分點(diǎn)，然后找使最大的切分點(diǎn)，容易想到這個(gè)切分點(diǎn)表示的是扎破氣球的位置。還有一種考慮的方式，就是說和不算在內(nèi)。那么方程現(xiàn)在變成，并且取不到邊界或者。

312. Burst Balloons

題目鏈接：https://leetcode.com/problems...

這題的dp方程還是挺難想的。首先subproblem比較容易：dp[i][j]: max coins I can get if there are balloons (i, j) left，有n^2個(gè)subproblem。接下來就是方程的問題了。

首先肯定是要遍歷切分點(diǎn)：k，然后max找使coin最大的切分點(diǎn)，容易想到這個(gè)切分點(diǎn)表示的是扎破氣球的位置。但是如果選擇這個(gè)位置作為區(qū)間(i, j)里面第一次扎破氣球的位置，問題就來了，扎破k之后，區(qū)間(i, j)內(nèi)部需要合并，一個(gè)式子看起來是沒法做的。所以轉(zhuǎn)換一下思路，設(shè)k是區(qū)間內(nèi)最后一個(gè)扎破的氣球，那么問題就簡單多了。k是區(qū)間內(nèi)最后一個(gè)的話，k現(xiàn)在相鄰的點(diǎn)就是i-1和j+1了，注意如果i = 0, j = n-1，要多帶帶討論下，還有分割點(diǎn)可以取左右邊界i或者j。

public class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;
        
        int[][] dp = new int[n][n];
        
        for(int len = 0; len < n; len++) {
            for(int i = 0; i < n - len; i++) {
                int j = i + len;
                for(int k = i; k <= j; k++) {
                    int l = i > 0 ? nums[i-1] : 1;
                    int r = j < n-1 ? nums[j+1] : 1;
                    int left = k - 1 >= i ? dp[i][k-1] : 0;
                    int right = k + 1 <= j ? dp[k+1][j] : 0;
                    dp[i][j] = Math.max(dp[i][j], l*nums[k]*r + left + right);
                }
            }
        }
        return dp[0][n-1];
    }
}

還有一種考慮subproblem的方式：dp[i][j]: : max coins I can get if there are balloons (i, j) left，就是說i和j不算在內(nèi)。那么dp方程現(xiàn)在變成：dp[i][j] = max(nums[i]*nums[k]*nums[j], dp[i][k] + dp[k][j])，并且k取不到邊界i或者j。這時(shí)候，base case結(jié)果就變了: dp[i][i] = 0, dp[i][i+1] = 0

參考discussion：
https://discuss.leetcode.com/...