2021-04-28：力扣546，移除盒子。给出一些不同颜色的盒子，盒子的颜色由数字表示，即不同的数字表示不同的颜色。你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k * k 个积分。当你将所有盒子都去掉之后，求你能获得的最大积分和。
福大大 答案2021-04-28：
动态规划。
代码用golang编写。代码如下：
package main
import (
"fmt"
)
func main() {
arr := []int{2, 2, 2}
ret := removeBoxes2(arr)
fmt.Println(ret)
}
func removeBoxes2(boxes []int) int {
N := len(boxes)
dp := make([][][]int, N)
for i := 0; i < N; i++ {
dp[i] = make([][]int, N)
for j := 0; j < N; j++ {
dp[i][j] = make([]int, N)
}
}
ans := process2(boxes, 0, N-1, 0, dp)
return ans
}
func process2(boxes []int, L int, R int, K int, dp [][][]int) int {
if L > R {
return 0
}
if dp[L][R][K] > 0 {
return dp[L][R][K]
}
// 找到开头，
// 1,1,1,1,1,5
// 3 4 5 6 7 8
// !
last := L
for last+1 <= R && boxes[last+1] == boxes[L] {
last++
}
// K个1 (K + last - L) last
pre := K + last - L
ans := (pre+1)*(pre+1) + process2(boxes, last+1, R, 0, dp)
for i := last + 2; i <= R; i++ {
if boxes[i] == boxes[L] && boxes[i-1] != boxes[L] {
ans = getMax(ans, process2(boxes, last+1, i-1, 0, dp)+process2(boxes, i, R, pre+1, dp))
}
}
dp[L][R][K] = ans
return ans
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}