[leetcode 312. Burst Ballons] hard |week 2

2019-11-06 07:25:02

字體：大中小

來源：轉載

供稿：網友

Burst Ballons

一、題目

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

二、思路分析

這個題目一開始我是很沒有頭緒的，因為不知道要從哪里開始。但是我看到了另外一個博客的一句話，“最后一個數將數組分為了兩部分”我就明白了這道題為什么會有分而治之的標簽，這是一道用到分而治之思想的動態規劃題。隨便拿一個數組來說，假如它的第i個數字是最后消除的那個數字，那么i的左邊跟右邊的數字在計算金幣值是毫不相關的因此可以看成兩個子問題，然后這兩個子問題再繼續求解。但是若直接用遞歸的方法，時間消耗很大，于是我想到了用動態規劃的方法，將結果保存在dp數組里， dp[k][l]表示從第k個數字到第l個數字能獲得的最大金幣值。最后通過三重循環就能讓dp[1][n]處的值即為答案。

三、代碼

class Solution {public: int maxCoins(vector<int>& nums) { vector<int>temp; int n=nums.size(); int **dp=new int*[n+2]; for(int i=0;i<n+2;i++) dp[i]=new int[n+2]; //開dp二維數組 for(int i=0;i<n+2;i++) for(int j=0;j<n+2;j++) dp[i][j]=0; temp.push_back(1); for(int i=0;i<n;i++){ temp.push_back(nums[i]); } temp.push_back(1); for(int length=1;length<=n;length++){ //三重循環 for(int b=1;b<=n-length+1;b++){ int e=b+length-1; for(int i=b;i<=e;i++){ dp[b][e]=max(dp[b][e],dp[b][i-1]+dp[i+1][e]+temp[i]*temp[b-1]*temp[e+1]); //通過遞推得出式子 } } } return dp[1][n];}};