戳气球
二 题目
有 n 个气球,编号为 0 到 n-1,
每个气球上都标有一个数字,
这些数字存在数组 nums 中。
现在要求你戳破所有的气球。
如果你戳破气球 i ,就可以获得 nums[left] * nums[i] * nums[right] 个硬币。
这里的 left 和 right 代表和 i 相邻的两个气球的序号。
注意当你戳破了气球 i 后,
气球 left 和气球 right 就变成了相邻的气球。
求所能获得硬币的最大数量。
说明:
你可以假设 nums[-1] = nums[n] = 1,
但注意它们不是真实存在的所以并不能被戳破。
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
示例:
输入: [3,1,5,8]
输出: 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
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/burst-balloons
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
/**
* @param {number[]} nums
* @return {number}
*/
var maxCoins = function(nums) {
};
根据上面的已知函数,小伙伴们可以先尝试破解本题,确定了自己的答案后再看下面代码。
三 解题思路
拿到题目,大脑开始运转:
// 思考:
// 如果数组长度大于 2,那就戳中间最小的数字。
// 例如:
// [3, 1, 5, 8] 戳 1(注意这里的中间是指 1, 5)
// [3, 5, 8] 戳 5 (注意这里的中间是指 5)
// 如果数组长度等于 2,那就先戳最小的,再戳最大的
// [3, 8] 先戳 3(1 * 3 * 8),再戳 8(1 * 8 * 1)
/**
* @param {number[]} nums
* @return {number}
*/
const maxCoins = (nums) => {
const length = nums.length;
// 如果没有
if (!length) {
return 0;
}
// 如果剩 1 个
if (length === 1) {
return 1 * nums[0] * 1;
}
// 如果剩 2 个
if (length === 2) {
if (nums[0] < nums[1]) {
return (1 * nums[0] * nums[1]) + (1 * nums[1] * 1);
} else {
return (nums[0] * nums[1] * 1) + (1 * nums[0] * 1);
}
}
// 如果剩 2 个以上
const minIndex = 0, min = 101; // 注意界限,气球的个数范围是 [0, 500],气球的数字范围是 [0, 100]
// 我们要戳的范围不包含 0 以及 length - 1,即范围:[1, length - 2]
for (let i = 1; i < length - 1; i++) {
if (nums[i] < min) {
min = nums[i];
minIndex = i;
}
}
return nums[minIndex - 1] * nums[minIndex] * nums[minIndex + 1];
};
console.log(maxCoins(
[3, 1, 5, 8],
));
这时候我们写了一遍基础的,即每次应该戳破的是哪个气球。
然后我们要做的,就是将其他累加起来,得到最终答案:
// 思考:
// 如果数组长度大于 2,那就戳中间最小的数字。
// 例如:
// [3, 1, 5, 8] 戳 1(注意这里的中间是指 1, 5)
// [3, 5, 8] 戳 5 (注意这里的中间是指 5)
// 如果数组长度等于 2,那就先戳最小的,再戳最大的
// [3, 8] 先戳 3(1 * 3 * 8),再戳 8(1 * 8 * 1)
/**
* @param {number[]} nums
* @return {number}
*/
const maxCoins = (nums) => {
let sum = 0;
const ergodic = (nums) => {
const length = nums.length;
console.log('------');
console.log(sum);
console.log(nums);
// 如果没有
if (!length) {
return;
}
// 如果剩 1 个
if (length === 1) {
sum += (1 * nums[0] * 1);
return;
}
// 如果剩 2 个
if (length === 2) {
if (nums[0] < nums[1]) {
sum += (1 * nums[0] * nums[1]) + (1 * nums[1] * 1);
return;
} else {
sum += (nums[0] * nums[1] * 1) + (1 * nums[0] * 1);
return;
}
}
// 如果剩 2 个以上
// 注意界限,气球的个数范围是 [0, 500],气球的数字范围是 [0, 100]
let minIndex = 0, min = 101;
// 我们要戳的范围不包含 0 以及 length - 1,即范围:[1, length - 2]
for (let i = 1; i < length - 1; i++) {
if (nums[i] < min) {
min = nums[i];
minIndex = i;
}
}
sum += (nums[minIndex - 1] * nums[minIndex] * nums[minIndex + 1]);
// 戳破这一个气球
nums.splice(minIndex, 1);
// 将剩下的带进去
ergodic(nums);
};
ergodic(nums);
return sum;
};
// console.log(maxCoins(
// [3, 1, 5, 8],
// )); // 167
console.log(maxCoins(
[9,76,64,21,97,60],
)); // 1086136
提交之后,我们发现在 “14 / 70 个通过测试用例” 中:
- 已知:
[9,76,64,21,97,60]
- 解出:721504
- 实际答案:1086136
这么说我们的思路有问题了。
仔细研究了下这个的戳破过程:
[60] [9,76,60] [9,75,64,97,60]
60 ——> 9 ——> 76 ——> 97 ——> 64 -> 21
[9,60] [9,75,97,60] [9,76,64,21,97,60]
即从 21 开始,一直到最后一个 60。
相比:
- 正确:21->64->97->76->9->60
- 错误:21->64->76->97->9->60
正确题解:
/**
* @param {number[]} nums
* @return {number}
*/
var maxCoins = function(nums) {
let n = nums.length
let dp = Array.apply(null, Array(n + 2)).map(t => Array(n + 2).fill(0))
nums = [1, ...nums, 1]
for(let i = n - 1; i >= 0; i--){
for(let j = i + 1; j < n + 2; j++){
for(let k = i + 1; k < j; k++){
let temp = dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]
dp[i][j] = Math.max(dp[i][j], temp)
}
}
}
console.log(dp);
return dp[0][n + 1];
};
// console.log(maxCoins(
// [3, 1, 5, 8],
// )); // 167
console.log(maxCoins(
[9,76,64,21,97,60],
)); // 1086136
四 统计分析
本题暂不能统计分析。
五 套路分析
如果小伙伴有更好的思路想法,或者没看懂其中某种解法,欢迎评论留言或者私聊 jsliang~
jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。