HackerRank #Lego Blocks

题目来自 HackerRank¹，给定了任意数量的四种砖块，高度都是 1，宽度分别为 1、2、3、4。需要用这些砖块填充一面 height x width 的墙，当然不能有重叠、不能有空缺。

限制是，墙的中间不允许存在一条竖线分开整面墙，不然左右两部分没有固定，整面墙不安全。

要求计算出共有多少种符合条件的拼接方式，结果可能比较大，对 10^9 + 7 取 MOD。

1"""
21 <= height, width <= 1000
3"""
4def legoBlocks(height: int, width: int) -> int:
5    pass

这种组合问题，尤其是只考虑高度为 1 时的组合，是典型的一个问题拆分成重复子问题，是 DP 没错。

如果没有不允许出现竖线的限制，我们可以直接算出 1 x width 的组合数 M，多层之间是独立的，最终结果就是 M^height 了。

但是这个竖线的限制很麻烦，竖线这里是对应总 height 的 global 状态，我们怎么在处理每一行的时候，基于这个 global 状态做状态转移呢？

从另一个 LeetCode 的题目 #554 Brick Wall² 找到了一点灵感。
这道题中，已经有了一个 height x width 的墙，我们希望在 [1, width - 1] 的范围里垂直切割，求破坏的砖块的最小数量。
解法中有一个小小的逆向思维，总共 height 层的切割过程中要么刚好穿过砖块的缝隙，要么破坏了砖块，那咱们忽略有没有破坏砖块了，只统计有没有穿过缝隙。

对于现在这道 Lego 题，咱们也逆向思维从竖线考虑。希望找到所有安全的组合数，我已经知道所有组合的总数量了，那就只用算出不安全的组合数，做个减法。

怎么算不安全的组合数呢？我们累计整面墙以坐标 a 对应的竖线拆开的组合数。如果 a 的位置有竖线，左边的宽度是 a，右边的宽度是 width - a，不安全的总数就是左边的组合数 x 右边的组合数，我们从总数量中减去这部分不安全的数量。

1┌──────│───────┐
2│      │       │
3│      │       │
4└──────│───────┘
5       a

如果最终组合里只有一条竖线，是没有问题的，但是如果有多条竖线，会导致同样的组合被减了多次。比如下面的例子，当我遍历到 a 时，右边的组合中包含了有 b 的情况，当遍历到 b 时，左边组合中包含有 a 的情况。

1┌────│────│────┐
2│    │    │    │
3│    │    │    │
4└────│────│────┘
5     a    b

对于遍历过程中唯一的坐标 x，怎么去除这个重复呢？我们可以从 2 个角度理解：

• 上面的例子，遍历到 b，左边有 a，那么 ab 同时存在这个情况一定之前考虑过了。
  换句话说，b 的左边有任何竖线，对应的情况都考虑过了。
  即 b 的左边不应该出现任何竖线。
• 在 [1, width - 1] 的遍历中，我想找到以 x 为第一条竖线的组合数量，这样一定不会有重复计算。
  x 的左边也不应该出现任何竖线。

好了，我们重新梳理一遍流程。

0. 我们希望求 height x width 对应的所有安全组合数。
1. 不方便直接计算安全的组合数，我们选择用所有组合数减去不安全的组合数。
2. 对于 1 x width 的组合数，是一维 DP 问题。
3. 高度为 height 的所有组合数，就是高度为 1 的结果 M^height。
4. 需要减去所有不安全的组合数，为了避免多次扣除，我们遍历 [1, width - 1]。
   对于每一个位置 x，我们希望求左边都是安全的，右边是任意的，对应的所有组合数，从总数中扣除。

那么就可以 coding 了：

 1from functools import cache
 2
 3MOD = 1_000_000_007
 4
 5@cache
 6def singleRowCount(width: int) -> int:
 7    if width == 0:
 8        return 1
 9    res = 0
10    for i in range(1, 5):
11        if width >= i:
12            res += singleRowCount(width - i)
13    return res
14
15@cache
16def unsafeCount(height: int, width: int) -> int:
17    return pow(singleRowCount(width), height, MOD)
18
19@cache
20def safeCount(height: int, width: int) -> int:
21    if width == 1:
22        return 1
23    res = unsafeCount(height, width)
24    # no break in left range, any in right range
25    for i in range(1, width):
26        res -= safeCount(height, i) * unsafeCount(height, width - i)
27        res %= MOD
28    return res
29
30def legoBlocks(height, width):
31    return safeCount(height, width)

AC 之后的碎碎念是：

• 之前在遇到不好描述状态时，总是往升维的角度去想。
  一道题里玩 2 种 DP，这还是第一次。
• 算法总是给人惊喜。
  新手的重点是培养自己的 coding 模板，保证正确性。
  等后面有了经验，就需要拆问题的直觉了，当然，还有出题人的想象力，笑〜