2021-04-28：力扣546，移除盒子。给出一些不同颜色的盒子

原创

福大大架构师每日一题

修改于 2021-05-04 22:25:45

4450

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
    }
}

执行结果如下：