这是 2020 年 8 月 15 日的每日一题。这道题我没写出来,是看题解的,这道题如果用常规的动态规划思路,很容易进入误区。特此记录一下。主要学到了以下两点:

  1. 动态规划的 dp 函数可以是多元的,当二元无法表达状态转移的时候,尝试加多一维,具体第三维可以表示什么,这道题给出了一种思路。
  2. 当动态规划的状态转移方向难以确定的时候,可以使用 递归 + 记忆化 的形式。虽然比迭代要占用更多的空间复杂度,但是好处是 递归 不用思考状态转移的方向。

题目

给出一些不同颜色的盒子,盒子的颜色由数字表示,即不同的数字表示不同的颜色。
你将经过若干轮操作去去掉盒子,直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子(k >= 1),这样一轮之后你将得到 k*k 个积分。
当你将所有盒子都去掉之后,求你能获得的最大积分和。

提示

  • 1 <= boxes.length <= 100
  • 1 <= boxes[i] <= 100

示例

输入: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 分)

思维误区

这道题一看,不用说肯定是动态规划。但如果你和我一样刷的题还不够多的话,就很容易会构造出这样一个 dp 函数

 dp(i, j) 表示移除 第 i 个到 第 j 个盒子能拿到的最多积分。

我一开始就是这么想的,然后开始思考状态转移。因为之前写过一道类似的题,是打气球,当你打爆一个气球的时候可以拿到当前气球以及周围两个一共是三个气球的积分。

那个情况因为每次涉及到的气球数量肯定是 1、2、3 。是可以确定的。所以可以直接使用类似的方法规定 dp 函数

但是这道题不一样,这道题每次涉及到的盒子数量是不确定的。例如以下情况:

boxes:  [1, 1, 1, 2, 1, 1]
index:   0, 1, 2, 3, 4, 5

当我先拿掉第 3 个 盒子的时候,剩下的移除盒子数量为 5 个。这种情况用以上的 dp 函数 其实是很难进行状态转移的。

这个点足以推翻整个思路过程。所以我甚至开始怀疑这道题不是用 动态规划 解。

题解

来看看官方题解的思路。

首先我们给 dp 函数 提升一下维度,三维函数:

dp(i, j, k) 表示 移除 第 i 个到 第 j 个盒子加上区间右边和 box[j] 一样颜色的 k 个盒子索能拿到的最大积分

这里解释一下,首先 ij 的意思和上面差不多。假设这里是盒子列表:

boxes:  [2, 1, 3, 2, 1, 3, 1, 1]
index:   0, 1, 2, 3, 4, 5, 6, 7

则此时 dp(0, 4, 2) 则表示以下区间:

2, 1, 3, 2, 1, 1, 1

首先是第 0 到 第 4 个盒子,右边再加上两个和 第 2 个盒子一样颜色的盒子。

这样我们就可以表示上面说的那一种不确定数量的情况了。

状态转移

首先我们发现,如果第 j 个盒子颜色等于 j-1 的盒子的话,也可以做一下转移,如果 boxes[j] == boxes[j-1] 的话,使 j-1 同时 k+1

这样处理后,以下操作都能保证 boxes[j] != boxes[j-1]

首先思考最简单的一种情况,因为 dp(i, j, k) 中最后 k+1 个盒子一定是一样颜色的,所以我们可以先把最后的 k+1 个盒子先移除在移除剩下部分:

[2, 1, 3, 2,] [1, 1, 1]

此时状态转移方程为:

dp(i ,j ,k) = dp(i, j-1, 0) + (k+1)^2

然后就比较灵活了,我们可以遍历 ij-1 的盒子,找到盒子颜色等于 boxes[j] 的盒子。然后将区间分成三部分,还是以以上的区间距离,我们遍历到 0 的时候,发现 boxes[1] = boxes[4]

所以我们可以这样拆分区间

[2, 1,] [3, 2,] [1, 1, 1]

然后我们可以先将中间部分移除,这样首尾就会合并。

所以此时的状态转移方程为:

dp(0, 4, 2) = dp(0, 1, 3) + dp(2, 3, 0)

所以对于全体,假设 boxes[n] = boxes[j],则状态转移方程为:

dp(i, j, k) = dp(i, n, k+1) + dp(n+1, j-1, 0)

好了,接下来我们把全部情况都合并一下,得到总的状态转移:

因为 latex 插件始终有点问题(总是要手动刷新一次公式才会显示),所以这里直接给出状态转移伪代码:

if(boxes[j] == boxes[j-1]){
    dp[i][j][k] = dp[i][j-1][k+1];
}else{
    dp[i][j][k] = dp[i][j-1][0] + (k+1)*(k+1);
    for(int n = i ; n < j ; n ++){
        if(boxes[n] == boxes[j]){
            dp[i][j][k] = max(
                dp[i][j][k],
                dp[i][n][k+1] + dp[n+1][j-1][0]
                );
        }
    }
}

边界条件

边界条件的话,这道题倒是没啥特殊的,首先肯定是 i < j 的时候,值是 0。其他的边界条件也不用怎么考虑。至于为啥不需要考虑是因为这次处理方式有点不一样。

状态转移方向

转移方向就比较难顶了,因为状态转移方程中有 j-1,有 k+1,还有一个遍历的 n ,所以这里的状态转移方向几乎是无法确定的。无法确定的话,就必须选择递归的写法了。当然,作为动态规划,肯定是要加上 记忆化 的。

代码

至此,代码也呼之欲出了,直接上:

  • 语言:C++
class Solution {
public:
    int removeBoxes(vector<int>& boxes) {
        vector<vector<vector<int>>> dp(
                boxes.size(), vector<vector<int>>(
                        boxes.size(), vector<int>(
                                boxes.size(), 0
                                )
                        )
                );

        return dfs(0, boxes.size()-1, 0, dp, boxes);
    }

    int dfs(int i, int j, int k, vector<vector<vector<int>>> &dp, vector<int>& boxes){
        if (j < i){
            return 0;
        }
        if(dp[i][j][k] != 0){
            return dp[i][j][k];
        }

        while(j > i && boxes[j] == boxes[j-1]){
            j --;
            k ++;
        }
        if(boxes[j] == boxes[j-1]){
            dp[i][j][k] = dfs(i, j-1, k+1, dp, boxes);
            return dp[i][j][k];
        }
        dp[i][j][k] = dfs(i, j-1, 0, dp, boxes) + (k+1)*(k+1);
        for(int n = i ; n < j ; n ++){
            if(boxes[n] == boxes[j]){
                dp[i][j][k] = max(
                        dp[i][j][k],
                        dfs(i,n,k+1, dp, boxes) + dfs(n+1, j-1, 0, dp, boxes)
                        );
            }
        }
        return dp[i][j][k];
    }
};

总结

动态规划的代码其实在 状态转移方程 的基础上不难理解,总的来说这题不算难,主要是提供了一种新的 状态转移 思路,也就是添加一个维度。这里还是放上我的两点总结吧:

  1. 动态规划的 dp 函数可以是多元的,当二元无法表达状态转移的时候,尝试加多一维,具体第三维可以表示什么,这道题给出了一种思路。
  2. 当动态规划的状态转移方向难以确定的时候,可以使用 递归 + 记忆化 的形式。虽然比迭代要占用更多的空间复杂度,但是好处是 递归 不用思考状态转移的方向。