[LeetCode] 312. Burst Balloons 打氣球游戲

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 iyou 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:

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

Example:

Input:

[3,1,5,8]

Output:

167

Explanation:

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

Credits:
Special thanks to @peisi for adding this problem and creating all test cases.

這道題提出了一種打氣球的游戲，每個氣球都對應(yīng)著一個數(shù)字，每次打爆一個氣球，得到的金幣數(shù)是被打爆的氣球的數(shù)字和其兩邊的氣球上的數(shù)字相乘，如果旁邊沒有氣球了，則按1算，以此類推，求能得到的最多金幣數(shù)。參見題目中給的例子，題意并不難理解。那么大家拿到題后，總是會習(xí)慣的先去想一下暴力破解法吧，這道題的暴力搜索將相當(dāng)?shù)膹?fù)雜，因為每打爆一個氣球，斷開的地方又重新挨上，所有剩下的氣球又要重新遍歷，這使得分治法不能 work，整個的時間復(fù)雜度會相當(dāng)?shù)母?，不要指望可以通過 OJ。而對于像這種求極值問題，一般都要考慮用動態(tài)規(guī)劃 Dynamic Programming 來做，維護(hù)一個二維動態(tài)數(shù)組 dp，其中 dp[i][j] 表示打爆區(qū)間 [i,j] 中的所有氣球能得到的最多金幣。題目中說明了邊界情況，當(dāng)氣球周圍沒有氣球的時候，旁邊的數(shù)字按1算，這樣可以在原數(shù)組兩邊各填充一個1，方便于計算。這道題的最難點(diǎn)就是找狀態(tài)轉(zhuǎn)移方程，還是從定義式來看，假如區(qū)間只有一個數(shù)，比如 dp[i][i]，那么計算起來就很簡單，直接乘以周圍兩個數(shù)字即可更新。如果區(qū)間里有兩個數(shù)字，就要算兩次了，先打破第一個再打破了第二個，或者先打破第二個再打破第一個，比較兩種情況，其中較大值就是該區(qū)間的 dp 值。假如區(qū)間有三個數(shù)呢，比如 dp[1][3]，怎么更新呢？如果先打破第一個，剩下兩個怎么辦呢，難道還要分別再遍歷算一下嗎？這樣跟暴力搜索的方法有啥區(qū)別呢，還要 dp 數(shù)組有啥意思。所謂的狀態(tài)轉(zhuǎn)移，就是假設(shè)已知了其他狀態(tài)，來推導(dǎo)現(xiàn)在的狀態(tài)，現(xiàn)在是想知道 dp[1][3] 的值，那么如果先打破了氣球1，剩下了氣球2和3，若之前已經(jīng)計算了 dp[2][3] 的話，就可以使用其來更新 dp[1][3] 了，就是打破氣球1的得分加上 dp[2][3]。那假如先打破氣球2呢，只要之前計算了 dp[1][1] 和 dp[3][3]，那么三者加起來就可以更新 dp[1][3]。同理，先打破氣球3，就用其得分加上 dp[1][2] 來更新 dp[1][3]。說到這里，是不是感覺豁然開朗了 ^.^

那么對于有很多數(shù)的區(qū)間 [i, j]，如何來更新呢？現(xiàn)在是想知道 dp[i][j] 的值，這個區(qū)間可能比較大，但是如果知道了所有的小區(qū)間的 dp 值，然后聚沙成塔，逐步的就能推出大區(qū)間的 dp 值了。還是要遍歷這個區(qū)間內(nèi)的每個氣球，就用k來遍歷吧，k在區(qū)間 [i, j] 中，假如第k個氣球最后被打爆，那么此時區(qū)間 [i, j] 被分成了三部分，[i, k-1]，[k]，和 [k+1, j]，只要之前更新過了 [i, k-1] 和 [k+1, j] 這兩個子區(qū)間的 dp 值，可以直接用 dp[i][k-1] 和 dp[k+1][j]，那么最后被打爆的第k個氣球的得分該怎么算呢，你可能會下意識的說，就乘以周圍兩個氣球被 nums[k-1] * nums[k] * nums[k+1]，但其實這樣是錯誤的，為啥呢？dp[i][k-1] 的意義是什么呢，是打爆區(qū)間 [i, k-1] 內(nèi)所有的氣球后的最大得分，此時第 k-1 個氣球已經(jīng)不能用了，同理，第 k+1 個氣球也不能用了，相當(dāng)于區(qū)間 [i, j] 中除了第k個氣球，其他的已經(jīng)爆了，那么周圍的氣球只能是第 i-1 個，和第 j+1 個了，所以得分應(yīng)為 nums[i-1] * nums[k] * nums[j+1]，分析到這里，狀態(tài)轉(zhuǎn)移方程應(yīng)該已經(jīng)躍然紙上了吧，如下所示：

dp[i][j] = max(dp[i][j], nums[i - 1] * nums[k] * nums[j + 1] + dp[i][k - 1] + dp[k + 1][j])                 ( i ≤ k ≤ j )

有了狀態(tài)轉(zhuǎn)移方程了，就可以寫代碼，下面就遇到本題的第二大難點(diǎn)了，區(qū)間的遍歷順序。一般來說，遍歷所有子區(qū)間的順序都是i從0到n，然后j從i到n，然后得到的 [i, j] 就是子區(qū)間。但是這道題用這種遍歷順序就不對，在前面的分析中已經(jīng)說了，這里需要先更新完所有的小區(qū)間，然后才能去更新大區(qū)間，而用這種一般的遍歷子區(qū)間的順序，會在更新完所有小區(qū)間之前就更新了大區(qū)間，從而不一定能算出正確的dp值，比如拿題目中的那個例子 [3, 1, 5, 8] 來說，一般的遍歷順序是：

[3] -> [3, 1] -> [3, 1, 5] -> [3, 1, 5, 8] -> [1] -> [1, 5] -> [1, 5, 8] -> [5] -> [5, 8] -> [8] 

顯然不是我們需要的遍歷順序，正確的順序應(yīng)該是先遍歷完所有長度為1的區(qū)間，再是長度為2的區(qū)間，再依次累加長度，直到最后才遍歷整個區(qū)間：

[3] -> [1] -> [5] -> [8] -> [3, 1] -> [1, 5] -> [5, 8] -> [3, 1, 5] -> [1, 5, 8] -> [3, 1, 5, 8]

這里其實只是更新了 dp 數(shù)組的右上三角區(qū)域，最終要返回的值存在 dp[1][n] 中，其中n是兩端添加1之前數(shù)組 nums 的個數(shù)。參見代碼如下：

解法一：

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
        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] = max(dp[i][j], nums[i - 1] * nums[k] * nums[j + 1] + dp[i][k - 1] + dp[k + 1][j]);
                }
            }
        }
        return dp[1][n];
    }
};

對于題目中的例子[3, 1, 5, 8]，得到的dp數(shù)組如下：

這題還有遞歸解法，思路都一樣，就是寫法略有不同，參見代碼如下：

解法二：

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
        return burst(nums, dp, 1 , n);
    }
    int burst(vector<int>& nums, vector<vector<int>>& dp, int i, int j) {
        if (i > j) return 0;
        if (dp[i][j] > 0) return dp[i][j];
        int res = 0;
        for (int k = i; k <= j; ++k) {
            res = max(res, nums[i - 1] * nums[k] * nums[j + 1] + burst(nums, dp, i, k - 1) + burst(nums, dp, k + 1, j));
        }
        dp[i][j] = res;
        return res;
    }
};

到此這篇關(guān)于C++實現(xiàn)LeetCode(312.打氣球游戲)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)打氣球游戲內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！