2021-04-28: force buckle 546, remove the box. Give some boxes of different colors

2021-04-28： Power button 546, Remove the box . Give some boxes of different colors , The color of the box is represented by numbers , That is, different numbers represent different colors . You will go through several rounds of operations to remove the box , Until all the boxes are removed . Each round you can remove a continuous with the same color k Boxes （k >= 1）, After such a round, you will get k * k Integral points . When you remove all the boxes , Find the maximum points you can get and .

Fuda answer 2021-04-28：

Dynamic programming .

The code to use golang To write . The code is as follows ：

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]
    }
    //  Find the beginning ,
    // 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 individual 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
    }
}

The results are as follows ：

picture

---

Zuo Shen java Code