2019獨角獸企業重金招聘Python工程師標準>>>

問題：

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

解決：

【題意】給定n個氣球。每次你可以打破一個，打破第i個，那么你會獲得nums[left] * nums[i] * nums[right]個積分。 （nums[-1] = nums[n] = 1）求你可以獲得的最大積分數。

① https://segmentfault.com/a/1190000007297715

動態規劃。dp[i][j]表示打爆區間[i,j]中的所有氣球能得到的最多金幣。DP的思想是bottom up

最后的剩下一個氣球為i的時候，可以獲得的分數為：nums[-1]*nums[i]*nums[n].

那么介于i , 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])

( i?≤?k?≤?j )，O(N^2), O(N^2)

class Solution { //15ms
? ? public static int maxCoins(int[] nums) {
? ? ? ? int[] tmpnums = new int[nums.length + 2];
? ? ? ? System.arraycopy(nums,0,tmpnums,1,nums.length);
? ? ? ? tmpnums[0] = 1;
? ? ? ? int len = tmpnums.length;
? ? ? ? tmpnums[len - 1] = 1;
? ? ? ? int[][] dp = new int[len][len];
? ? ? ? for (int l = 2;l < len;l ++){
? ? ? ? ? ? for (int i = 0;i < len - l;i ++){
? ? ? ? ? ? ? ? int j = i + l;
? ? ? ? ? ? ? ? for (int k = i + 1;k < j;k ++){
? ? ? ? ? ? ? ? ? ? dp[i][j] = Math.max(dp[i][j],tmpnums[i] * tmpnums[k] * tmpnums[j] + dp[i][k] + dp[k][j]);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return dp[0][len - 1];
? ? }
}

②?D&C + Memorization，O(N^3) , O(N^2)

memorization是from top to bottom，每一次都將值分成兩部分，然后分別計算。對于在left和right中間的位置i，考慮[left,i]和[i,right]能組成的部分，分別對這兩部分進行遞歸求值。用二維數組記錄已經計算過的值，避免重復計算。

class Solution { //10ms
? ? public static int maxCoins(int[] nums) {
? ? ? ? int[] tmpnums = new int[nums.length + 2];
? ? ? ? for (int i = 1;i <= nums.length;i ++){
? ? ? ? ? ? tmpnums[i] = nums[i - 1];
? ? ? ? }
? ? ? ? tmpnums[0] = 1;
? ? ? ? tmpnums[tmpnums.length - 1] = 1;
? ? ? ? int len = tmpnums.length;
? ? ? ? int[][] memo = new int[len][len];
? ? ? ? return burst(tmpnums,0,len - 1,memo);
? ? }
? ? public static int burst(int[] nums,int i,int j,int[][] memo){
? ? ? ? if (i + 1 == j) return 0;//[i,j]之間沒有ballon可以炸掉
? ? ? ? if (memo[i][j] > 0){//如果已經計算過了，則直接返回
? ? ? ? ? ? return memo[i][j];
? ? ? ? }
? ? ? ? int res = 0;
? ? ? ? for (int k = i + 1;k < j;k ++){
? ? ? ? ? ? res = Math.max(res,nums[i] * nums[k] * nums[j] + burst(nums,i,k,memo) + burst(nums,k,j,memo));//遞歸獲取左右窗口的最大值
? ? ? ? }
? ? ? ? memo[i][j] = res;
? ? ? ? return res;
? ? }
}

轉載于:https://my.oschina.net/liyurong/blog/1593682

總結

以上是生活随笔為你收集整理的打破气球所能获得的最大积分 Burst Balloons的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。