C++如何實(shí)現(xiàn)打氣球游戲

這篇文章主要講解了“C++如何實(shí)現(xiàn)打氣球游戲”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“C++如何實(shí)現(xiàn)打氣球游戲”吧！

打氣球游戲

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.

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

那么對(duì)于有很多數(shù)的區(qū)間 [i, j]，如何來更新呢？現(xiàn)在是想知道 dp[i][j] 的值，這個(gè)區(qū)間可能比較大，但是如果知道了所有的小區(qū)間的 dp 值，然后聚沙成塔，逐步的就能推出大區(qū)間的 dp 值了。還是要遍歷這個(gè)區(qū)間內(nèi)的每個(gè)氣球，就用k來遍歷吧，k在區(qū)間 [i, j] 中，假如第k個(gè)氣球最后被打爆，那么此時(shí)區(qū)間 [i, j] 被分成了三部分，[i, k-1]，[k]，和 [k+1, j]，只要之前更新過了 [i, k-1] 和 [k+1, j] 這兩個(gè)子區(qū)間的 dp 值，可以直接用 dp[i][k-1] 和 dp[k+1][j]，那么最后被打爆的第k個(gè)氣球的得分該怎么算呢，你可能會(huì)下意識(shí)的說，就乘以周圍兩個(gè)氣球被 nums[k-1] * nums[k] * nums[k+1]，但其實(shí)這樣是錯(cuò)誤的，為啥呢？dp[i][k-1] 的意義是什么呢，是打爆區(qū)間 [i, k-1] 內(nèi)所有的氣球后的最大得分，此時(shí)第 k-1 個(gè)氣球已經(jīng)不能用了，同理，第 k+1 個(gè)氣球也不能用了，相當(dāng)于區(qū)間 [i, j] 中除了第k個(gè)氣球，其他的已經(jīng)爆了，那么周圍的氣球只能是第 i-1 個(gè)，和第 j+1 個(gè)了，所以得分應(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ū)間。但是這道題用這種遍歷順序就不對(duì)，在前面的分析中已經(jīng)說了，這里需要先更新完所有的小區(qū)間，然后才能去更新大區(qū)間，而用這種一般的遍歷子區(qū)間的順序，會(huì)在更新完所有小區(qū)間之前就更新了大區(qū)間，從而不一定能算出正確的dp值，比如拿題目中的那個(gè)例子 [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)該是先遍歷完所有長(zhǎng)度為1的區(qū)間，再是長(zhǎng)度為2的區(qū)間，再依次累加長(zhǎng)度，直到最后才遍歷整個(gè)區(qū)間：

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

這里其實(shí)只是更新了 dp 數(shù)組的右上三角區(qū)域，最終要返回的值存在 dp[1][n] 中，其中n是兩端添加1之前數(shù)組 nums 的個(gè)數(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];
    }
};

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

0    0    0    0       0     0
0    3    30  159  167  0
0    0    15  135  159  0
0    0    0    40     48   0
0    0    0    0       40   0
0    0    0    0       0     0

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

解法二：

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;
    }
};

感謝各位的閱讀，以上就是“C++如何實(shí)現(xiàn)打氣球游戲”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)C++如何實(shí)現(xiàn)打氣球游戲這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！