摘要:之后該氣球?qū)⑾В瑥亩渥笥覂蓚€(gè)氣球成為相鄰的氣球。這意味著的時(shí)間復(fù)雜度。這樣就違背了分治法將問(wèn)題分解為獨(dú)立問(wèn)題的要求。此時(shí)得到的子隊(duì)列長(zhǎng)度等于,因此將無(wú)法拆解,即結(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
這里講了一個(gè)炸氣球小游戲的規(guī)則。當(dāng)我們選中一個(gè)氣球并炸掉它后,會(huì)得到該氣球以及其相鄰兩個(gè)氣球的分?jǐn)?shù)的乘積,并加入我們的積分。之后該氣球?qū)⑾В瑥亩渥笥覂蓚€(gè)氣球成為相鄰的氣球。問(wèn)如何選擇氣球才能使得積分?jǐn)?shù)最高。
思路和代碼我直接解釋一下看到的最高票的回答。
如果采用暴力法的話,我們會(huì)遍歷出所有可能的結(jié)果,并且比較其最終獲得最高積分值。這意味著O(n!)的時(shí)間復(fù)雜度。
如果采用動(dòng)態(tài)規(guī)劃法的話,我們?cè)谥懒苏ǖ鬹個(gè)氣球之后的最大積分,然后計(jì)算炸掉k+1個(gè)氣球的最大積分。時(shí)間依舊感人。
這里采用的是backtracking+分治法來(lái)解決。當(dāng)我們正向思考這道題時(shí),我們可能會(huì)想,隨機(jī)選擇一個(gè)氣球,按該氣球作為分界線分為兩個(gè)子氣球隊(duì)列。這時(shí)再分別計(jì)算左右兩個(gè)隊(duì)列可以得到的最大積分。
但是這里有一個(gè)問(wèn)題在于,左邊隊(duì)列炸掉氣球的順序可能會(huì)影響到右邊氣球的順序,比如假設(shè)存在這樣一列氣球?qū)?yīng)的積分為3,2,4,1,5,我們?nèi)?作為分界點(diǎn),分為兩個(gè)子數(shù)組3,2,1,5那么如果左邊氣球炸掉的順序?yàn)?b>2,3,則右邊隊(duì)列的最左側(cè)值則會(huì)先是2,再是3。這樣就違背了分治法將問(wèn)題分解為獨(dú)立問(wèn)題的要求。因此這種思路無(wú)法解決該問(wèn)題。
但是如果反過(guò)來(lái)思考,假設(shè)我們先選取最后一個(gè)炸掉的氣球,那么我們知道這個(gè)獲得的積分一定是nums[i]*nums[left]*nums[right],則以該氣球作為分界點(diǎn)將隊(duì)列分解后獲得的兩個(gè)子隊(duì)列的邊界是一定的。舉個(gè)例子3,2,4,1,5:
首先,我們將其填充為1,3,2,4,1,5,1
然后我們將隊(duì)列從2分解開來(lái),即2是最后一個(gè)炸掉的氣球,那么該氣球的積分?jǐn)?shù)為1*2*1
自隊(duì)列分別為1,3,2和2,4,1,5,1。
那么假設(shè)我們?cè)俨鸾?b>1,3,2中的3,則結(jié)果為1*3*2。此時(shí)得到的子隊(duì)列長(zhǎng)度等于2,因此將無(wú)法拆解,即結(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)注我的微信公眾號(hào)!將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://m.specialneedsforspecialkids.com/yun/68842.html
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...
摘要:接下來(lái)就是方程的問(wèn)題了。首先肯定是要遍歷切分點(diǎn),然后找使最大的切分點(diǎn),容易想到這個(gè)切分點(diǎn)表示的是扎破氣球的位置。還有一種考慮的方式,就是說(shuō)和不算在內(nèi)。那么方程現(xiàn)在變成,并且取不到邊界或者。 312. Burst Balloons 題目鏈接:https://leetcode.com/problems... 這題的dp方程還是挺難想的。首先subproblem比較容易:dp[i][j]: ...
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
摘要:找規(guī)律復(fù)雜度時(shí)間空間思路由于我們只要得到第個(gè)全排列,而不是所有全排列,我們不一定要將所有可能都搜索一遍。根據(jù)全排列順序的性質(zhì),我們可以總結(jié)出一個(gè)規(guī)律假設(shè)全排列有個(gè)數(shù)組成,則第個(gè)全排列的第一位是。然后將得到,這個(gè)就是下一輪的。 Permutation Sequence The set [1,2,3,…,n] contains a total of n! unique permutati...
摘要:題目地址題目描述給出集合,其所有元素共有種排列。說(shuō)明給定的范圍是。第二種是回溯法求全排列,設(shè)置一個(gè)全局變量為當(dāng)前求出的排列數(shù),求出第個(gè)全排列,也就是時(shí),停止所有遞歸否則會(huì)超時(shí)。 題目地址:https://leetcode-cn.com/probl...題目描述:給出集合 [1,2,3,…,n],其所有元素共有 n! 種排列。 按大小順序列出所有排列情況,并一一標(biāo)記,當(dāng) n = 3 時(shí),...
閱讀 2032·2021-11-08 13:14
閱讀 2940·2021-10-18 13:34
閱讀 2029·2021-09-23 11:21
閱讀 3591·2019-08-30 15:54
閱讀 1760·2019-08-30 15:54
閱讀 2931·2019-08-29 15:33
閱讀 2581·2019-08-29 14:01
閱讀 1948·2019-08-29 13:52