铺砖问题

Reading Time: 3 minutes

这是昨天读 <<挑战程序设计竞赛>> 的时候看到的一个状态压缩动态规划, 书上写的文字内容其实挺好懂的, 但是初次读程序的时候花了一些时间才完全理解了这个题. 实际上我并没有在网上找到过这个程序的正确解释, 我写这篇文章的时候找到的三个解释 (解释一 解释二 解释三) 都有一定的问题

前两个解释属于完全没有看懂书上在写啥的, 而解释三提供了一种额外的解法, 参考了 hiho1048, 但是 hiho1048 这个题的列数 m 最多只有5, 所以可以使用一个 $O(nm(2^{m})^2)$ 的做法. 但是书上这个题的 m 是15, 解释三的做法是一定超时的.

由于这个状压 DP 的状压方式比较少见, 所以在这里做个记录.

首先我们看一下题面:

铺砖问题

给定 $n\times m$ 的格子,每个格子被朵成了黑色或者白色。现在要用 $1\times 2$ 的砖块覆盖这些格子,要求块与块之间互相不重叠, 且覆盖了所有白色的格子,但不覆盖任意一个黑色格子。求一共有多少种覆盖方法,输出方案数对 $M$ 取余后的结果。

限制条件

$1\lt n,m \lt 15$

$2 \leq M \leq {10}^9$

这里对书上的解释做一个更详细的叙述, 建议结合书本食用.

书中一开始给出了一个基于 DFS 的做法, 我们可以用一个数组 $used[i][j]$ 来表示位于坐标 $(i,j)$ 的格子是否有瓷砖覆盖, 注意按照这个定义, 一个黑色格子 (即 $color[i][j]==true$ ) 的 $used[i][j]$ 必为 $0$, 因为上面不能有瓷砖.

由于这个题本身肯定不能是一个纯 DFS, 所以我们一定要把这个程序改造成一个记忆化搜索或者说是动态规划, 那么为了更好地观察这个 DFS, 我们需要将所有可能影响到 DFS 函数结果的变量全部都设置成参数, 这样方便我们明确状态数, 也方便 DP 的状态设计.

这个 DFS 的代码相当好懂, 值得一提的是我们如果要在扫描到某个格子 $(i,j)$ 的时候放置砖块, 那么如果横着放, 一定是占据 $(i,j) (i,j+1)$, 如果是竖着放, 一定是占据 $(i,j) (i+1,j)$.

如书中所示, 这个 DFS 过程一共要输入以下三个参数, $i$, $j$ 以及 $used$ 数组. 其中 $i\in[0,n-1]$, $j\in[0,m-1]$, $used$ 可以被看做一个有 $n\times m$ 个位的二进制数. 所以 $used\in[0,2^{n\times m}-1]$, 这意味着如果我们直接地使用记忆化搜索, 那么我们需要开一个大小为 $n\times m\times2^{n\times m}$ 的数组, 这显然是不可接受的.

如果要减少状态数量, 那么我们就要考虑有哪些参数实际上是没有被使用到的.

简单考虑我们就可以发现 $used$ 数组其实没有那么多位, 至少我们知道, 黑色的格子对应的 $used$ 一定是 $0$.

以及我们为了防止重复计数肯定是有一个扫描顺序的, 由于每个格子都应该要被覆盖到. 所以我们从左上角往右下角开始扫描. 已经被扫过的格子, 如果是白色的, 那么就是一定被覆盖的. 所以实际上我们没有必要在 $used$ 数组中存储已经扫描过的格子的状态.

又由于我们的砖块只有 $1\times2$ 的大小, 所以有大量的格子我们是根本不可能已经放过砖块的. 如下图所示:

        j
    0 1 2 3 4
  0 * * * * *
i 1 * * X ? ?
  2 ? ? . . .
  3 . . . . .
  4 . . . . .

假设我们当前已经扫描到了 $(i,j)$, 也就是 X 的位置, 那么如前文所述, 已经被扫描过的格子 * 中的白色格子是一定被覆盖了的, 由于我们刚扫描到 $(i,,j)$ 这个位置的时候, 还没有在 X 这个位置上放置过瓷砖, 所以 .的部分是一定没有放置瓷砖的. 整个地图中唯一可能影响到当前这个 DFS 的结果的部分只有每一列从上向下数遇到的第一个没有被扫描过的格子的状态. 也就是 X?的部分, 可以看到, 这个部分只有 $m$ 个格子.

所以理论上来说, 我们可以让整个 DFS 的参数变成 $i,j,used’$, 其中 $used’$ 这个一维数组的容量只有 $m$, 其中 $used'[k]$ 表示: 当扫描到 $(i,j)$ 这个位置的时候, 第 $k$ 列从上向下数第一个还没有被扫描到的格子是否被瓷砖覆盖.

这个新的 DFS 过程就已经很方便记忆化搜索了. 但是我们可以直接给它写成 DP.

注意到这个 DFS 和大部分的 DP 都不一样, 这个 DFS 过程实际上返回的答案是: “在格子$(i,j)$ 之前的白色格子都已经被覆盖的情况下, 当前每列的从上向下数第一个没有被扫描过的格子的瓷砖覆盖情况为 $used’$ 的情况下, 覆盖完所有白色格子的方案数量”.

这意味着我们就可以按照上面那个描述来设计状态, 那么设计出来的状态就是 $dp[i][j][used]$ 由于我们每次需要得到格子 $(i,j)$ 对于所有的 $used$ 的答的时候只会使用到 $(i,j)$ 的下一个单元格比如说如果不换行的话就是 $(i,j+1)$ 这个格子对应的 $dp[i][j+1]$ 这个以 $used$ 为下标的一维数组. 诸如 $dp[i][j+2]$ 之类的数据已经不起作用, 所以我们可以直接用滚动数组把前两维 $i$ 和 $j$ 都滚了.

所以实际上 $i,j$ 越大, 问题规模是越小的.

我们做 DP 写成递推的话, 肯定是先做小问题,再往大问题递推. 所以我们在做 DP 的过程中需要把循环的方向反过来. 从右下角开始向左上方递推.

点名批评 这篇文章

//...
int *now=dp[0],*nex=dp[1];
now[0]=1;
for(int i=n-1;i>=0;i--){
  //从n-1 开始会方便二进制表示状态
  for(int j=m-1;j>=0;j--){
    for(int used=0;used< (1<<m) ;used++){
      //遍历状态,这里反过来表示
      if(used>>j & 1 || M[i][j]){
        //假如这个位置被用了或者是1 不用填
        nex[used]=now[used & ~(1<<j)];
//...

这个地方给我造成了很大的误解, “n-1 开始会方便二进制表示状态” 这句话我一开始看的时候理解为”这个从 $n-1$ 开始往 $0$ 走的循环方向可以方便用二进制表示状态.” 我现在大概理解作者所说的是 “从0开始到n-1的编号方式, 比从1开始到n的编号方式更方便二进制表示集合状态”.

那么现在我们可以开始阅读书上的程序了. 这里为了方便我个人的理解 对换了书中代码中的 crt 和 next 变量名. 具体看代码注释:

int dp[2][1 << MAX_M]; // 滚动数组
void solve () {
  int *next= dp [0], *crt = dp [1];
  // crt 为 dp[i][j],
  // 当 j!=m-1 时 next 为 dp[i][j+1],
  //              否则 为 dp[i+1][0].
  next[0] = 1; // 初始化
  // 注意到当 i=n-1,j=m-1 的时候,
  // next 实际上是并不存在的 dp[n][0].
  // 所以 next[0] 此时实际上存放 dfs(n,0,0)的返回值.
  // 对应书前面的 dfs 代码可知, 结果为1.
  // 这表示已经找到了一种覆盖方案.
  for (int i = n - 1; i >= 0; i--) {
    for (int j = m - 1; j >= 0; j--) {
      for (int used = 0; used < 1<<m; used++) {
        // 遍历所有可能的 used
        if ( (used>>j & 1) || color[i][j]) {
          // 如果我当前扫到的这个格子上已经被放置了瓷砖,
          // 或者这个格子本身是黑的,
          // 那么就不用再在这里放瓷砖了,
          // 我们应该直接扫描下一个格子.
          // 当前格子被放过了瓷砖,
          // 可能是由于这个格子左边的格子横着放了一个瓷砖,
          // 也可能是因为上面的格子竖着放了一个瓷砖.
          // 对应书中未优化的 dfs 代码,
          // 我们不需要对 used 数组做任何修改,
          // 但是这里却需要更改,
          // 因为这里的 used 和之前代码中的 used 不同,
          // 在扫描的过程中,
          // i,j 变化的时候 used 对应的格子发生了变化.
          // 如下图所示, 我们扫描到 (i,j) 的时候,
          // used 对应的是 (2,0) (2,1) (1,2) (1,3) (1,4)
          //          j
          //     0 1 2 3 4
          //   0 * * * * *
          // i 1 * * X ? ?
          //   2 ? ? . . .
          //   3 . . . . .
          //   4 . . . . .
          // 而如下图所示, 再接着递归时,
          // 我们需要扫描格子 (i,j+1) 时,
          // used 对应的是 (2,0) (2,1) (2,2) (1,3) (1,4)
          //           j
          //     0 1 2 3 4
          //   0 * * * * *
          // i 1 * * * X ?
          //   2 ? ? ? . .
          //   3 . . . . .
          //   4 . . . . .
          // 注意到 used[2] 的意义发生了变化,
          // 本来是格子 (1,2) 现在却是 (2,2) 了,
          // 我们并没有在 (i,j) 处放瓷砖,
          // 这意味着新出现在 used 数组中的
          // 格子 (i+1,j) 一定是没有被放过瓷砖的状态.
          // 所以将其置0, 然后递归.
          ctr[used] = next[used & ~(l << j)];
        } else {
          // 如果进入到这里, 那么意味着
          // 当前这个格子 (i,j) 是一个白色的空格子, 需要放置砖块.
          int res = 0;
          if (j + 1 < m && !( used>>(j+1) & 1) && !color[i][j + 1]) {
            // 如果我们要横着放,
            // 那么我们首先得保证有横着放的空间.
            // 当我们横放的时候, 我们会占用 (i,j+1) 这个格子,
            // 所以我们将其置1,
            // 由于我们没有竖着放, 所以(i+1,j) 一定是空的,
            // 这意味着新的 used 的第 j 位并没有更新的必要,
            // 它本来就是0 [注意上面的 else 下方的注释]
            res+= next[used | 1 << (j + 1)];
          }
          // 竖着放
          if (i + 1 < n && !color[i + 1][j]) {
              res+= next[used | 1 << j];
          }
          crt[used] = res % M;
        }
      }
      swap(crt, next);
    }
  }
  printf("%d\n", next[0]);
  // 当我们完成循环以后,
  // 我们实际上需要的答案是 dp[0][0][0],
  // 最后一次循环的时候
  // dp[0][0] 实际上是crt,
  // 但是由于多跑了一次 swap, 所以现在是 next 了
}

这里留三个问题, 供读者确定自己理解到位:

  1. 这个程序是如何处理换行的问题的呢?
  2. 试分析竖着放的递推式的意义?
  3. 如何用记忆化搜索的形式改写这个程序?

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注