以下是 LeetCode LCP 04. 覆盖 的 Python3 实现。题目分析- 棋盘大小n × m1 ≤ n, m ≤ 8- 坏掉的格子broken 数组给出- 目标用 1×2 的多米诺骨牌可横放或竖放覆盖完好格子求最多能放多少块由于棋盘很小最大 8×8适合用 轮廓线 DP逐格 DP解决。核心思路轮廓线 DP轮廓线 DP 是逐格进行状态转移的动态规划。维护一个长度为 m 的状态字符串表示当前处理位置上方 m 个格子的覆盖情况- 0该位置空闲可以放新骨牌- 1该位置已被占用被骨牌覆盖或是坏掉的格子对于每个格子 (i, j)有三种转移方式转移 条件 操作 骨牌数不放 总是可行 当前格子状态加入轮廓线 不变横放 j 0 且左边格子空闲 (st[-1] 0) 覆盖当前格子和左边格子 1竖放 上方格子空闲 (st[0] 0) 覆盖当前格子和上方格子 1Python3 实现pythonfrom typing import Listfrom collections import Counter, defaultdictclass Solution:def domino(self, n: int, m: int, broken: List[List[int]]) - int:轮廓线DP (逐格DP)状态: 一个长度为m的字符串表示当前轮廓线状态0 该位置空闲可以放骨牌1 该位置已被占用被覆盖或是坏掉的格子# A[i][j] 0 表示格子(i,j)完好# A[i][j] 1 表示格子(i,j)坏掉A [[0] * m for _ in range(n)]for i, j in broken:A[i][j] 1# ct: 当前轮廓线状态 - 最大骨牌数# 初始状态所有m个位置都视为已被覆盖即全1骨牌数为0ct Counter({1 * m: 0})for i in range(n):for j in range(m):ct2 defaultdict(int)for st in ct:# st 是当前轮廓线状态长度为m的字符串# 转移1: 当前格子不放置骨牌# 将st左移一位去掉最左边加入当前格子的状态st2 st[1:] A[i][j]ct2[st2] max(ct2[st2], ct[st])# 转移2和3: 当前格子放置骨牌前提是当前格子完好if A[i][j] 0:# 转移2: 横着放与左边格子组成骨牌# 需要当前格子左边即st的最后一个字符是0# 且当前不是第一列j 0if j 0 and st[-1] 0:# 横放骨牌当前格子和左边格子都被覆盖st2 st[1:-1] 11ct2[st2] max(ct2[st2], ct[st] 1)# 转移3: 竖着放与上方格子组成骨牌# 需要st的第一个字符是0上方格子是空闲的if st[0] 0:# 竖放骨牌当前格子被覆盖上方格子也被覆盖st2 st[1:] 1ct2[st2] max(ct2[st2], ct[st] 1)ct ct2# 返回所有状态中的最大值return max(ct.values())复杂度分析- 时间复杂度O(n \cdot m \cdot 2^m)。状态数为 2^m每个状态有常数种转移。- 空间复杂度O(2^m)。只需维护当前列的状态空间。验证结果输入 输出n2, m3, broken[[1,0],[1,1]] 2n3, m3, broken[] 4n1, m2, broken[] 1n2, m2, broken[] 2
