312. Burst Balloons

calx 發布于2019-08-19 10:45 / 2493人閱讀

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

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個subproblem。接下來就是方程的問題了。

首先肯定是要遍歷切分點：k，然后max找使coin最大的切分點，容易想到這個切分點表示的是扎破氣球的位置。但是如果選擇這個位置作為區間(i, j)里面第一次扎破氣球的位置，問題就來了，扎破k之后，區間(i, j)內部需要合并，一個式子看起來是沒法做的。所以轉換一下思路，設k是區間內最后一個扎破的氣球，那么問題就簡單多了。k是區間內最后一個的話，k現在相鄰的點就是i-1和j+1了，注意如果i = 0, j = n-1，要多帶帶討論下，還有分割點可以取左右邊界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不算在內。那么dp方程現在變成：dp[i][j] = max(nums[i]*nums[k]*nums[j], dp[i][k] + dp[k][j])，并且k取不到邊界i或者j。這時候，base case結果就變了: dp[i][i] = 0, dp[i][i+1] = 0

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/76402.html

[LeetCode] 312. Burst Balloons

Problem Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get...

TerryCai 2019-08-16 13:53 評論0 收藏0
leetcode 312. Burst Balloons

摘要：之后該氣球將消失，從而其左右兩個氣球成為相鄰的氣球。這意味著的時間復雜度。這樣就違背了分治法將問題分解為獨立問題的要求。此時得到的子隊列長度等于，因此將無法拆解，即結束。題目要求 Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by arr...

pinecone 2019-08-15 14:49 評論0 收藏0
312. Burst Balloons

public class Solution { public int maxCoins(int[] nums) { int n = nums.length; int[] newNum = new int[n+2]; newNum[0] = 1; newNum[n+1] = 1; for(int i=0; i

wyk1184 2019-08-16 10:36 評論0 收藏0
css-in-js 探討

摘要：庫通過在中插入標簽在運行時創建樣式。結論是一體化的樣式解決方案，用于彌合和之間的差距。零運行時解決方案通過恢復工具來緩解一些缺點，這些工具將討論提升到更有趣的水平。 Web開發是需要掌握多種技術。我們習慣于與多種語言密切合作。而且，隨著開發Web應用程序變得越來越普遍和差別細微化，我們經常尋找創造性的方法來彌合這些語言之間的差距，從而使我們的開發環境和工作流程更容易，更高效。最常見的...

Scliang 2019-08-30 15:54 評論0 收藏0
解析React SSR 中的限流案例

　　本篇文章主要為大家講述關于ReactSSR之限流，其實我們都知道React SSR是涉及到服務端的，因此，我們先需要考慮到很多的服務器端問題，下面就為大家舉例說明。　　當簡單來說， React 的應用進行頁面加載或 SEO 優化時，都會想到React SSR。也就會想到服務器端，這是必須考慮到的。　　現在我們來說下所謂限流，其實是在我們的服務資源有限、處理能力有限時，通過對請求或并發數進行限制...

3403771864 2023-03-17 08:28 評論0 收藏0