以下是 LeetCode LCP 04. 覆盖 的 JavaScript 实现。题目分析- 棋盘大小n × m1 ≤ n, m ≤ 8- 坏掉的格子broken 数组给出- 目标用 1×2 的多米诺骨牌可横放或竖放覆盖完好格子求最多能放多少块使用 轮廓线 DP逐格 DP解决。由于 m ≤ 8状态可以用 m 位二进制数表示。核心思路轮廓线 DP逐格处理棋盘维护一个长度为 m 的轮廓线状态位 含义bit 0 (最低位) 当前格子上方的格子用于竖放判断bit m-1 (最高位) 当前格子左边的格子用于横放判断状态转移1. 不放置轮廓线右移当前格子状态加入末尾2. 横放左边格子空闲bit m-1 0覆盖当前格子和左边格子3. 竖放上方格子空闲bit 0 0覆盖当前格子和上方格子JavaScript 实现javascript/*** param {number} n* param {number} m* param {number[][]} broken* return {number}*/var domino function(n, m, broken) {// a[i][j] false 表示格子(i,j)完好// a[i][j] true 表示格子(i,j)坏掉const a Array.from({ length: n }, () Array(m).fill(false));for (const [bi, bj] of broken) {a[bi][bj] true;}// dp: Mapstate, max_domino_count// 状态用m位二进制数表示// bit k 0: 该位置空闲可以放骨牌// bit k 1: 该位置已被占用被骨牌覆盖或是坏掉的格子//// bit 0 (最低位) - 当前格子上方的格子用于竖放判断// bit (m-1) (最高位) - 当前格子左边的格子用于横放判断let dp new Map();dp.set((1 m) - 1, 0); // 初始: 全1状态所有位置视为已占用for (let i 0; i n; i) {for (let j 0; j m; j) {const ndp new Map();for (const [st, cnt] of dp) {const isBroken a[i][j];// 转移1: 不放置骨牌// 轮廓线右移一位去掉 bit 0当前格子状态加入为新的 bit (m-1)const newBit isBroken ? 1 : 0;const nextSt1 ((st 1) | (newBit (m - 1))) ((1 m) - 1);ndp.set(nextSt1, Math.max(ndp.get(nextSt1) || 0, cnt));// 当前格子完好时尝试放置骨牌if (!isBroken) {// 转移2: 横着放与左边格子组成骨牌// 需要: j 0 且左边格子空闲 (st 的最高位为 0)if (j 0 ((st (m - 1)) 1) 0) {// 横放后: 当前格子和左边格子都被覆盖// 保留中间位设置最后两位为 1const mask m 2 ? (1 (m - 2)) - 1 : 0;const nextSt2 (((st 1) mask) | (3 (m - 2))) ((1 m) - 1);ndp.set(nextSt2, Math.max(ndp.get(nextSt2) || 0, cnt 1));}// 转移3: 竖着放与上方格子组成骨牌// 需要: 上方格子空闲 (st 的最低位为 0)if ((st 1) 0) {// 竖放后: 当前格子被覆盖上方格子已在当前 st 中被覆盖const nextSt3 ((st 1) | (1 (m - 1))) ((1 m) - 1);ndp.set(nextSt3, Math.max(ndp.get(nextSt3) || 0, cnt 1));}}}dp ndp;}}// 返回所有状态中的最大值let ans 0;for (const cnt of dp.values()) {ans Math.max(ans, cnt);}return ans;};复杂度分析- 时间复杂度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[] 2n8, m8, broken[] 32