问题描述
给定一个数组，表示气球的数字，当戳破一个编号为 i 的气球时，可以获得金币 nums[i - 1] * nums[i] * nums[i + 1] （如果 nums[i - 1] 或 nums[i + 1] 不存在，则值为 1），要求找出戳破气球所能获得的最大金币数量。题目链接：点我
样例输入输出
输入：nums = [3,1,5,8]
输出：167
解释：nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> []、coins = 315 + 358 + 138 + 181 = 167
输入：nums = [1,5]
输出：10
问题解法
此题如果使用暴力手法列出所有可能的情况，则会存在超时。需要用动态规划的解法进行求解。用 dp[i][j] 表示 i 到 j 中戳破气球所能获得的金币最大数（不包括边界 i 和 j），用 k 表示 i~j 中最后一个戳破的气球，则存在动态转移方程：dp[i][j] = dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]。注意 dp[i][j] 中是不包含边界 i、j 气球的。代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int maxCoins(int[] nums) {
int[][] dp = new int[nums.length + 2][nums.length + 2];
int[] values = new int[nums.length + 2];
for (int i = 0; i < nums.length; i++) {
values[i + 1] = nums[i];
}
values[0] = 1;
values[nums.length + 1] = 1;
for (int i = values.length - 3; i >= 0; i--) {
for (int j = i + 2; j < values.length; j++) {
for (int k = i + 1; k < j; k++) {
dp[i][j] = Math.max(dp[i][j], values[i] * values[k] * values[j] + dp[i][k] + dp[k][j]);
}
}
}
return dp[0][values.length - 1];
}
}
|
参考资料
https://leetcode.cn/problems/burst-balloons/solution/zhe-ge-cai-pu-zi-ji-zai-jia-ye-neng-zuo-guan-jian-/