题目:
有 n 个气球,编号为 0 到 n-1,每个气球上都标有一个数字,这些数字存在数组 nums 中。
现在要求你戳破所有的气球。如果你戳破气球 i ,就可以获得 nums[left] x nums[i] x nums[right] 个硬币。这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后,气球 left 和气球 right 就变成了相邻的气球。
求所能获得硬币的最大数量。
输入: [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
思路
实现
/**
* @param {number[]} nums
* @return {number}
*/
var maxCoins = function (nums) {
let _result = 0
function maxItem(list, result) {
if (list.length === 0) {
_result = Math.max(_result, result)
return
}
for (let i = 0; i < list.length; i++) {
let item = (list[i - 1] || 1) * list[i] * (list[i + 1] || 1)
maxItem(
list.filter((val, index) => index !== i),
result + item
)
}
}
maxItem(nums, _result)
return _result
}
每一个起点都计算了所有可能的组合,超时也在意料之中。想到优化,优先想到的是能不能存储下已经出现过的组合,发现 i 变换的过程中左右的元素也在变化似乎没有维度可以存储。
那换个思路,不存储点,存储范围试一下:
怎么得到 dp[i][j]的值?
实现
/**
* @param {number[]} nums
* @return {number}
*/
var maxCoins = function (nums) {
// 填充收尾默认的1,在添加后取length生成dp
nums.unshift(1)
nums.push(1)
let len = nums.length,
dp = Array.from({ length: len }, () => new Array(len).fill(-1))
// 去除添加的两个1,i和j的范围即要求的值
return solve(0, len - 1)
function solve(i, j) {
// 超出范围 返回0
if (i >= j - 1) return 0
// 该范围已经计算过
if (dp[i][j] != -1) return dp[i][j]
for (let k = i + 1; k < j; k++) {
let sum = nums[i] * nums[k] * nums[j]
sum += solve(i, k) + solve(k, j)
dp[i][j] = Math.max(dp[i][j], sum)
}
return dp[i][j]
}
return dp[0][len - 1]
}
# | 3 | 1 | 5 | 8 |
---|---|---|---|---|
3 | null | dp[0][1]->0 | dp[0][2]->0 | dp[0][3]->0 |
1 | null | null | dp[1][2]->1 | dp[1][3]->0 |
5 | null | null | null | dp[2][3]->1 |
8 | null | null | null | null |
会发现,i 需要从大到小变量
/**
* @param {number[]} nums
* @return {number}
*/
var maxCoins = function (nums) {
nums.unshift(1)
nums.push(1)
let len = nums.length,
dp = Array.from({ length: len }, () => new Array(len).fill(0))
// 默认填充的1不能被戳破,则i的边界为len-2-1
// (i<j,则i最大为len-1,去除默认则未len-2-1)
for (let i = len - 3; i >= 0; i--) {
// i<j,则j最小为i,去除默认则未i+1
for (let j = i + 2; j < len; j++) {
for (let k = i + 1; k < j; k++) {
dp[i][j] = Math.max(
dp[i][j],
dp[i][k] + nums[i] * nums[k] * nums[j] + dp[k][j]
)
}
}
}
return dp[0][len - 1]
}