一天一大 lee(移除盒子)难度:困难-Day20200815
题目:[1]
给出一些不同颜色的盒子，盒子的颜色由数字表示，即不同的数字表示不同的颜色。你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k*k 个积分。当你将所有盒子都去掉之后，求你能获得的最大积分和。
示例
输入：boxes = [1,3,2,2,2,3,4,3,1]
输出：23
解释：
[1, 3, 2, 2, 2, 3, 4, 3, 1]
----> [1, 3, 3, 4, 3, 1] (3*3=9 分)
----> [1, 3, 3, 3, 1] (1*1=1 分)
----> [1, 1] (3*3=9 分)
----> [] (2*2=4 分)
提示
- 1 <= boxes.length <= 100
- 1 <= boxes[i] <= 100
抛砖引玉
抛砖引玉
思路
题目的逻辑为：每次移除连续相同字符，求每次移除个数的最大平方和
逻辑复杂的点为移除字符后字符连续情况可能发生变化
移除的思路：指定一点查询与其相同的元素，遇到与其不同的元素时：
- 在移除这个指定元素时先优先移除遇到的不同元素，使指定元素连续
- 切换指定元素，开始查询新的指定元素的连续个数
每次移除元素均取两种移除方式得到的最大值
- 动态规划使用 dp(i,j,k):
- i，j 是区间索引
- k 组件内最后一个元素(boxes[j])连续出现的次数
- dp(i,j,k)表示区间 i 到 j 的结果
- i->j 区间，可以指定移除边界元素(boxes[i]或 boxes[j])
- 使用方法 1 移除时，dp(i,j,k)由区间外指定元素个数的平方(k+1)*(k+1) + 新区间的值 dp(i,j-X,0) （X 为 i-j 区间移除连续指定元素形成的区间）
- 使用方法 2 移除时，已知指定元素已经存在 k 个，遍历区间遇到等于指定元素的则从该位置分割子区间，优先移除隔离连续指定元素的区间 A，使连续 k 与存在相同元素的区间连接 B A = (i, x, k + 1) B = (x + 1, j - 1, 0)
实现
- 声明 dp 三维数组：dp[i][j][k]
- 从最大的区间即：0->len-1,开始计算
- 计算连续（选择一个方向:从先向后或者从后向前）
- 指定区间的结果 = 被移除连续个数评分+移除后剩余区间的结果：dp[i][j][k] = getNum(boxes, dp, i, j - 1, 0) + (k + 1) * (k + 1)
- 枚举子区间：i->x->j(使用索引 x 截取子区间) 在 boxes[x]===boxes[j]时：就形成了一个风格区间点 i->j 至少包含一个元素等于 boxes[j]，当该区间包含多个元素等于 boxes[j]时，为了避免重复计算值直接 dp 中取出
特殊情况
/**
* @param {number[]} boxes
* @return {number}
*/
var removeBoxes = function (boxes) {
let len = boxes.length,
dp = Array()
for (let i = 0; i < len; i++) {
dp[i] = new Array(len)
for (let j = 0; j < len; j++) {
dp[i][j] = new Array(len).fill(0)
}
}
function getNum(boxes, dp, i, j, k) {
if (i > j) return 0
// 区间计算过则直接返回
if (dp[i][j][k] != 0) return dp[i][j][k]
// 统计区间内连续子元素数量
while (i > j && boxes[j] === boxes[j - 1]) {
j--
k++
}
// 递归得到指定区间l->j的结果
dp[i][j][k] = getNum(boxes, dp, i, j - 1, 0) + (k + 1) * (k + 1)
// 在区间内枚举可能的存在的子区间
for (let x = i; x < j; x++) {
if (boxes[x] === boxes[j]) {
// dp[i][j][k]保存不同移除顺序下的最大值
dp[i][j][k] = Math.max(
dp[i][j][k],
getNum(boxes, dp, i, x, k + 1) + getNum(boxes, dp, x + 1, j - 1, 0)
)
}
}
return dp[i][j][k]
}
return getNum(boxes, dp, 0, len - 1, 0)
}参考资料
[1]
题目:: https://leetcode-cn.com/problems/remove-boxes/
举报
腾讯云开发者
