546. 移除盒子【DP】

题目

分析：暴力法

以1121134为例，肯定要尽量地将不连续的块连续起来，一并删除。这样收益较大。因为(1+1)^2 > 1^2 + 1^2。
这题很明显，应先删2,11和11连起来，然后一起删掉，然后删34。
当然也可以删34，再删2，再删1111。
这一题如果是暴力法的话，可以用ij遍历数组，遇到相同的消掉，然后用递归处理剩余的，如：
1121134
选11初始值2^2 + remove(21134)
选1（第二个）比较大小：res, 1+remove(121134)
选2 比较大小res, 1+remove(111134)
选第二组1，res,4+remove(11234)
……
递归可以减小问题的规模，最终进行求解！
时间复杂度空间复杂度，递归深度！

分析DP

我们要降低问题规模（数组大小）+记忆化搜索
为了降低复杂程度，我们可以从一头像另一头出发，比如重尾到头
321444
上述的例子，先删除3、2、1，收益是一样的

4321444
就有两种策略，先删除后面的444，再消除4321
先删除321，再消除4

DP是啥？
dp[l][r][k]
l表示起始下标，r表示结束下标，k表示与第r个元素相似的元素下标
rmBoxs
5432211
5412211如果是这种状态(541)2211 l=0 r=2 k=0
5412211 （22被干掉）l=0 r=2 k=2
5412211 （22被干掉）l=0 r=2 k=1

代码

//var dp map[int]map[int]map[int]int
type DP map[int]map[int]map[int]int // 三个key：l、r、k，对应c的三维数组

// 移除盒子
func removeBoxes(boxes []int) int {
    dp := make(map[int]map[int]map[int]int)
    return calculatePoints(boxes, dp, 0, len(boxes)-1, 0)
}

// dp
func calculatePoints(boxes []int, dp DP, l, r, k int) int {
    if l > r {
        return 0
    }

    // nil map可读
    if dp[l][r][k] != 0 {
        return dp[l][r][k]
    }

    // eg: Xl, Xl+1, ..., Xi,...,Xr,[6,6,6(0或多个)]
    // 如有尾部有若干和Xr相同的，则r左右
    for r>l && boxes[r-1] == boxes[r] {
        r--  // r左移
        k++  // 相同的数量增加
    }

    // 当前l，r的位置处，后面有k个与Xr相同的box
    // 策略1，把后k+1个消掉，前面l到r-1递归，这是一种策略，作为初始值
    // 访问dp[l][r][k]，nil Map不可写！
    if dp[l] == nil {
        dp[l] = make(map[int]map[int]int)
    }

    if dp[l][r] == nil {
        dp[l][r] = make(map[int]int)
    }
    // 策略1作为初始值
    dp[l][r][k] = calculatePoints(boxes, dp, l, r-1, 0) + (k+1)*(k+1)

    // 策略2，后k+1个保留，与Xi合并
    for i:=l; i<r; i++ {
        if boxes[i] == boxes[r] {  // 如果Xi == Xr
            // 分成两段：i+1,r-1,k==0消掉，使Xi与Xr合并;
            //          l, i,k=k+1(不是k+2，k是r后面与r相同的，现在r是i，i后面有k+1个)
            newGrade := calculatePoints(boxes, dp, i+1, r-1, 0) + calculatePoints(boxes, dp, l, i, k+1)
            if newGrade > dp[l][r][k] {
                dp[l][r][k] = newGrade
            }
        }
    }

    return dp[l][r][k]
}

总结

1、type DP map[int]map[int]map[int]int 可当三维数组使用
2、Map空的可读
3、Map空的不可写

最后编辑于：2020.06.19 09:39:20