07/23 12:39

# Burst Balloons (H)

## 题目

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
``````

## 思路

\[dp[left,\ right]=\max_{left \le i \le right}(dp[left,\ i-1]+dp[i+1,\ right]+nums[left-1]*nums[i]*nums[right+1]) \]

## 代码实现

### Java

#### 记忆化搜索

``````class Solution {
public int maxCoins(int[] nums) {
int[][] memo = new int[nums.length][nums.length];
for (int i = 0; i < nums.length; i++) {
Arrays.fill(memo[i], -1);
}
return dfs(nums, 0, nums.length - 1, memo);
}

private int dfs(int[] nums, int left, int right, int[][] memo) {
if (right < left) {
return 0;
}
if (memo[left][right] != -1) {
return memo[left][right];
}
int max = 0;
for (int i = left; i <= right; i++) {
int x = dfs(nums, left, i - 1, memo)
+ dfs(nums, i + 1, right, memo)
+ nums[i] * (left == 0 ? 1 : nums[left - 1]) * (right == nums.length - 1 ? 1 : nums[right + 1]);
max = Math.max(max, x);
}
memo[left][right] = max;
return max;
}
}
``````

#### 动态规划

``````class Solution {
public int maxCoins(int[] nums) {
if (nums.length == 0) {
return 0;
}

int[][] dp = new int[nums.length][nums.length];
for (int right = 0; right < nums.length; right++) {
for (int left = right; left >= 0; left--) {
for (int i = left; i <= right; i++) {
int leftMax = i == left ? 0 : dp[left][i - 1];
int rightMax = i == right ? 0 : dp[i + 1][right];
int last = nums[i] * (left == 0 ? 1 : nums[left - 1]) * (right == nums.length - 1 ? 1 : nums[right + 1]);
dp[left][right] = Math.max(dp[left][right], leftMax + rightMax + last);
}
}
}
return dp[0][nums.length - 1];
}
}
``````

1
0 收藏

07/23 12:43

1 评论
0 收藏
1