資訊專欄INFORMATION COLUMN
Problem
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:
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
Solution
class Solution {
public int maxCoins(int[] nums) {
int len = nums.length;
int[][] dp = new int[len][len];
return helper(nums, 0, len-1, dp);
}
private int helper(int[] nums, int start, int end, int[][] dp) {
if (start > end) return 0;
if (dp[start][end] != 0) return dp[start][end];
int max = 0;
for (int i = start; i <= end; i++) {
int curMax = helper(nums, start, i-1, dp) +
get(nums, i)*get(nums, start-1)*get(nums, end+1) +
helper(nums, i+1, end, dp);
max = Math.max(max, curMax);
}
dp[start][end] = max;
return max;
}
private int get(int[] nums, int i) {
if (i < 0 || i >= nums.length) return 1;
return nums[i];
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/72520.html
摘要：之后該氣球?qū)⑾?，從而其左右兩個(gè)氣球成為相鄰的氣球。這意味著的時(shí)間復(fù)雜度。這樣就違背了分治法將問題分解為獨(dú)立問題的要求。此時(shí)得到的子隊(duì)列長度等于，因此將無法拆解，即結(jié)束。 題目要求 Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by arr...
摘要：接下來就是方程的問題了。首先肯定是要遍歷切分點(diǎn)，然后找使最大的切分點(diǎn)，容易想到這個(gè)切分點(diǎn)表示的是扎破氣球的位置。還有一種考慮的方式，就是說和不算在內(nèi)。那么方程現(xiàn)在變成，并且取不到邊界或者。 312. Burst Balloons 題目鏈接：https://leetcode.com/problems... 這題的dp方程還是挺難想的。首先subproblem比較容易：dp[i][j]: ...
public class Solution { public int maxCoins(int[] nums) { int n = nums.length; int[] newNum = new int[n+2]; newNum[0] = 1; newNum[n+1] = 1; for(int i=0; i
摘要：找規(guī)律復(fù)雜度時(shí)間空間思路由于我們只要得到第個(gè)全排列，而不是所有全排列，我們不一定要將所有可能都搜索一遍。根據(jù)全排列順序的性質(zhì)，我們可以總結(jié)出一個(gè)規(guī)律假設(shè)全排列有個(gè)數(shù)組成，則第個(gè)全排列的第一位是。然后將得到，這個(gè)就是下一輪的。 Permutation Sequence The set [1,2,3,…,n] contains a total of n! unique permutati...
摘要：題目地址題目描述給出集合，其所有元素共有種排列。說明給定的范圍是。第二種是回溯法求全排列，設(shè)置一個(gè)全局變量為當(dāng)前求出的排列數(shù)，求出第個(gè)全排列，也就是時(shí)，停止所有遞歸否則會超時(shí)。 題目地址：https://leetcode-cn.com/probl...題目描述：給出集合 [1,2,3,…,n]，其所有元素共有 n! 種排列。 按大小順序列出所有排列情況，并一一標(biāo)記，當(dāng) n = 3 時(shí),...
閱讀 669·2023-04-25 15:49
閱讀 3121·2021-09-22 15:13
閱讀 1262·2021-09-07 10:13
閱讀 3484·2019-08-29 18:34
閱讀 2567·2019-08-29 15:22
閱讀 513·2019-08-27 10:52
閱讀 691·2019-08-26 18:27
閱讀 3028·2019-08-26 13:44
