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
題意
打氣球游戲，每個氣球有對應的分值，打爆一個氣球i，能得到的積分為氣球i、氣球i-1、氣球i+1積分的乘積，要求計算能夠獲得的最大積分，
思路
動態規劃問題，dp[left, right]表示打爆從left到right所有氣球能得到的最大積分，每一次我們在[left, right]這個區間中選擇一個i，代表該區間中最后一個被打爆的氣球，那么可以得到遞推關系式：
\[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];
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/17903.html
標籤：其他
下一篇：Unity-遇到的問題小總結