本題用記憶化搜索或者動態(tài)規(guī)劃
零、閑聊
找完工作有一個多月了，一直在咸魚。11月了，不能再繼續(xù)這樣了。編程題還要繼續(xù)刷，感覺一段時間不寫，思維確實沒有之前靈活了。所以以后還是不斷刷題，不斷學(xué)習(xí)。
一、題目
有 n 個氣球，編號為0 到 n-1，每個氣球上都標(biāo)有一個數(shù)字，這些數(shù)字存在數(shù)組 nums 中。
現(xiàn)在要求你戳破所有的氣球。每當(dāng)你戳破一個氣球 i 時，你可以獲得 nums[left] * nums[i] * nums[right] 個硬幣。 這里的 left 和 right 代表和 i 相鄰的兩個氣球的序號。注意當(dāng)你戳破了氣球 i 后，氣球 left 和氣球 right 就變成了相鄰的氣球。
求所能獲得硬幣的最大數(shù)量。
說明:
你可以假設(shè) nums[-1] = nums[n] = 1，但注意它們不是真實存在的所以并不能被戳破。
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
示例:
輸入: [3,1,5,8]
輸出: 167
解釋: nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 315 + 358 + 138 + 181 = 167
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/burst-balloons
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
二、分析
2.1 題目分析
這道題是很典型的動態(tài)規(guī)劃題。對于這類題，我也是一直沒有太多思路?？戳艘幌麓笊竦?a target="_blank">講解，感覺明白了一些。
那這篇博客中我們就從最基礎(chǔ)的深度優(yōu)先遍歷，到記憶化搜索，最后到動態(tài)規(guī)劃。三種方法來解決這道題。
2.2 深度優(yōu)先搜索
題目中氣球順序放置，每次扎破一個氣球。那么我們在程序中可以使用鏈表表示氣球，每次扎破一個氣球，就從鏈表中刪除一個結(jié)點。使用深度優(yōu)先搜索+回溯遍歷所有可能的情況。這樣肯定可以找到最優(yōu)解，但是時間復(fù)雜度是n！，數(shù)據(jù)量大的時候肯定會超時的。
代碼如下
//方法一：深度優(yōu)先搜索，使用鏈表存儲氣球，然后
public int maxCoins(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
List<Integer> src = new LinkedList<Integer>(); //鏈表保存氣球
src.add(1);
for (int i = 0; i < nums.length; i++) {
src.add(nums[i]);
}
src.add(1);
return loop(src);
}
private int loop(List<Integer> src) {
if (src.size() <= 2) { //遞歸的終止條件
return 0;
}
int res = 0;
for (int i = 1; i < src.size() - 1; i++) { //遍歷當(dāng)前每一個結(jié)點
int cur = src.get(i);
int temp = src.get(i - 1) * cur * src.get(i + 1); //計算戳爆該結(jié)點得到的硬幣數(shù)量
src.remove(i); //刪除該結(jié)點
res = Math.max(res, temp + loop(src)); //遞歸剩下的氣球，求出剩下的氣球能得到的最大硬幣數(shù)量
src.add(i, cur); //回溯，添加上該結(jié)點
}
return res;
}
深度優(yōu)先搜索可以找到最優(yōu)解，但是時間復(fù)雜度是n!，是因為重復(fù)計算了某些子問題。比如，對于[3, 1, 5, 8]這個氣球序列，如果我們用深度優(yōu)先搜索來解，將[5, 8]這個子問題重復(fù)計算了兩次。
2.3 記憶化搜索
簡單的深度優(yōu)先搜索重復(fù)計算了子問題，那么我們可以使用數(shù)組將子問題的結(jié)果保存下來。
但是在劃分子問題的時候有個小技巧
比如對于[3, 1, 5, 8]，可以先戳爆[1]，然后剩下[3]， [5, 8]兩個子問題。但是這有問題的，[3]和[5, 8]不是兩個獨立的子問題，他們相互關(guān)聯(lián)的，因為戳爆一個氣球，剩下的氣球又連在一起了，3右邊的氣球應(yīng)該是5。
這時候我們反向思維，對于[3, 1, 5, 8]，我們可以最后戳爆[1]，這樣[3] 和 [5, 8]兩個子問題之間就沒有關(guān)聯(lián)了。這里比較饒，大家可以看一下這個視頻，講的很好。
這時候我們可以寫出狀態(tài)轉(zhuǎn)移方程
for (int k = start; k <= end; k++) {
res = max(res, helper(start, k - 1) + src[start - 1] * src[k] * src[end + 1] + helper(k + 1, end));
}
并且把每一個子問題的解都保存到dp中。
下面看代碼
//方法二 記憶化搜索
List<Integer> src = null; //保存氣球的數(shù)組
int[][] dp = null; //dp數(shù)組
int len = 0;
public int maxCoins(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
len = nums.length;
dp = new int[len + 2][len + 2];
src = new ArrayList<Integer>();
src.add(1);
for (int i : nums) {
src.add(i);
}
src.add(1);
return loop(1, len);
}
private int loop(int start, int end) {
if (start > end) {
return 0;
}
if (dp[start][end] > 0) { //如果有緩存的解，直接返回
return dp[start][end];
}
int res = 0;
for (int k = start; k <= end; k++) { //搜索最優(yōu)解
//由于我們假設(shè)第k個氣球是最后戳破的，所有戳破他的時候他的左邊和右邊的氣球分別是start - 1和end + 1
res = Math.max(res, src.get(start - 1) * src.get(k) * src.get(end + 1) + loop(start, k - 1) + loop(k + 1, end));
}
dp[start][end] = res; //將結(jié)果保存到數(shù)組中
return res;
}
2.4 動態(tài)規(guī)劃
記憶化搜索將子問題的解緩存到數(shù)組中，當(dāng)遞歸到相同的子問題時，從緩存中讀取，相當(dāng)于進(jìn)行深度優(yōu)先搜索時進(jìn)行減枝。還是自頂向下的順序進(jìn)行搜索，只不過遞歸到某些已經(jīng)計算過的子問題時不用重復(fù)計算了。
我們可以自底向上進(jìn)行計算，先把最基礎(chǔ)的子問題計算完成，然后逐層網(wǎng)上計算，最后計算出來結(jié)果。
比如我們先計算長度為1的氣球序列的解，然后計算長度為2的氣球序列的解，逐層往上。
代碼如下
//動態(tài)規(guī)劃
public int maxCoins(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
List<Integer> list = new ArrayList<Integer>();
list.add(1);
for (int i : nums) {
list.add(i);
}
list.add(1);
int dp[][] = new int[n + 2][n + 2];
for (int len = 1; len <= n; len++) { //逐漸增大計算的粒度
for (int i = 1; i <= n - len + 1; i++) { //計算所有該粒度的子問題
int j = i + len - 1;
for (int k = i; k <= j; k++) { //計算子問題
dp[i][j] = Math.max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + list.get(i - 1) * list.get(k) * list.get(j + 1));
}
}
}
return dp[1][n];
}
