国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

leetcode 312. Burst Balloons

pinecone / 568人閱讀

摘要：之后該氣球?qū)⑾?，從而其左右兩個氣球成為相鄰的氣球。這意味著的時間復(fù)雜度。這樣就違背了分治法將問題分解為獨(dú)立問題的要求。此時得到的子隊列長度等于，因此將無法拆解，即結(jié)束。

題目要求 
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 nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note: 
(1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Given [3, 1, 5, 8]

Return 167

nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

這里講了一個炸氣球小游戲的規(guī)則。當(dāng)我們選中一個氣球并炸掉它后，會得到該氣球以及其相鄰兩個氣球的分?jǐn)?shù)的乘積，并加入我們的積分。之后該氣球?qū)⑾?，從而其左右兩個氣球成為相鄰的氣球。問如何選擇氣球才能使得積分?jǐn)?shù)最高。

思路和代碼

我直接解釋一下看到的最高票的回答。

如果采用暴力法的話，我們會遍歷出所有可能的結(jié)果，并且比較其最終獲得最高積分值。這意味著O(n!)的時間復(fù)雜度。

如果采用動態(tài)規(guī)劃法的話，我們在知道了炸掉k個氣球之后的最大積分，然后計算炸掉k+1個氣球的最大積分。時間依舊感人。

這里采用的是backtracking+分治法來解決。當(dāng)我們正向思考這道題時，我們可能會想，隨機(jī)選擇一個氣球，按該氣球作為分界線分為兩個子氣球隊列。這時再分別計算左右兩個隊列可以得到的最大積分。
但是這里有一個問題在于，左邊隊列炸掉氣球的順序可能會影響到右邊氣球的順序，比如假設(shè)存在這樣一列氣球?qū)?yīng)的積分為3，2，4，1，5,我們?nèi)?作為分界點，分為兩個子數(shù)組3,2,1,5那么如果左邊氣球炸掉的順序為2,3，則右邊隊列的最左側(cè)值則會先是2，再是3。這樣就違背了分治法將問題分解為獨(dú)立問題的要求。因此這種思路無法解決該問題。

但是如果反過來思考，假設(shè)我們先選取最后一個炸掉的氣球，那么我們知道這個獲得的積分一定是nums[i]*nums[left]*nums[right]，則以該氣球作為分界點將隊列分解后獲得的兩個子隊列的邊界是一定的。舉個例子3,2,4,1,5：
首先，我們將其填充為1,3,2,4,1,5,1
然后我們將隊列從2分解開來，即2是最后一個炸掉的氣球，那么該氣球的積分?jǐn)?shù)為1*2*1
自隊列分別為1,3,2和2,4,1,5,1。
那么假設(shè)我們再拆解1,3,2中的3，則結(jié)果為1*3*2。此時得到的子隊列長度等于2，因此將無法拆解，即結(jié)束。

    public int maxCoins(int[] nums) {
        int[] modifiedNums = new int[nums.length + 2];
        int n = 1;
        for(int num : nums){modifiedNums[n++] = num;}
        modifiedNums[0] = modifiedNums[n++] = 1;
        
        int[][] memo = new int[n][n];
        return maxCoins(modifiedNums, 0, n-1, memo);
    }
    
    public int maxCoins(int[] nums, int left, int right, int[][] memo){
        if(left+1 >=right) return 0;
        if(memo[left][right] != 0) return memo[left][right];
        int res = 0;
        for(int i = left+1; i


想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/68842.html

相關(guān)文章

  • [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 評論0 收藏0

  • 312. Burst Balloons

    摘要：接下來就是方程的問題了。首先肯定是要遍歷切分點，然后找使最大的切分點，容易想到這個切分點表示的是扎破氣球的位置。還有一種考慮的方式，就是說和不算在內(nèi)。那么方程現(xiàn)在變成，并且取不到邊界或者。 312. Burst Balloons 題目鏈接：https://leetcode.com/problems... 這題的dp方程還是挺難想的。首先subproblem比較容易：dp[i][j]: ...

    calx 評論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 評論0 收藏0

  • [Leetcode] Permutation Sequence 全排列序列

    摘要：找規(guī)律復(fù)雜度時間空間思路由于我們只要得到第個全排列，而不是所有全排列，我們不一定要將所有可能都搜索一遍。根據(jù)全排列順序的性質(zhì)，我們可以總結(jié)出一個規(guī)律假設(shè)全排列有個數(shù)組成，則第個全排列的第一位是。然后將得到，這個就是下一輪的。 Permutation Sequence The set [1,2,3,…,n] contains a total of n! unique permutati...

    testHs 評論0 收藏0

  • 力扣(LeetCode)756

    摘要：題目地址題目描述給出集合，其所有元素共有種排列。說明給定的范圍是。第二種是回溯法求全排列，設(shè)置一個全局變量為當(dāng)前求出的排列數(shù)，求出第個全排列，也就是時，停止所有遞歸否則會超時。 題目地址：https://leetcode-cn.com/probl...題目描述：給出集合 [1,2,3,…,n]，其所有元素共有 n! 種排列。 按大小順序列出所有排列情況，并一一標(biāo)記，當(dāng) n = 3 時,...

    Keven 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<