LCP 04：覆盖（★★）

2019-09-26 约 436 字预计阅读 1 分钟次阅读

力扣第 LCP 04 题

题目

你有一块棋盘，棋盘上有一些格子已经坏掉了。你还有无穷块大小为1 * 2的多米诺骨牌，你想把这些骨牌不重叠地覆盖在完好的格子上，请找出你最多能在棋盘上放多少块骨牌？这些骨牌可以横着或者竖着放。

输入：n, m代表棋盘的大小；broken是一个b * 2的二维数组，其中每个元素代表棋盘上每一个坏掉的格子的位置。

输出：一个整数，代表最多能在棋盘上放的骨牌数。

示例 1：

输入：n = 2, m = 3, broken = [[1, 0], [1, 1]]
输出：2
解释：我们最多可以放两块骨牌：[[0, 0], [0, 1]]以及[[0, 2], [1, 2]]。（见下图）

示例 2：

输入：n = 3, m = 3, broken = []
输出：4
解释：下图是其中一种可行的摆放方式

限制：

1 <= n <= 8
1 <= m <= 8
0 <= b <= n * m

分析

典型的轮廓线dp，遍历到某位置，按不放、竖着放、横着放分类递推即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution:
    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:
        A = [['0']*m for _ in range(n)]
        for i,j in broken:
            A[i][j] = '1'
        ct = Counter({'1'*m:0})
        for i in range(n):
            for j in range(m):
                ct2 = defaultdict(int)
                for st in ct:
                    st2 = st[1:]+A[i][j]
                    ct2[st2] = max(ct2[st2],ct[st])
                    if A[i][j]=='0':
                        if j and st[-1]=='0':
                            st2 = st[1:-1]+'11'
                            ct2[st2] = max(ct2[st2],ct[st]+1)
                        if st[0]=='0':
                            st2 = st[1:]+'1'
                            ct2[st2] = max(ct2[st2],ct[st]+1)
                ct = ct2
        return max(ct.values())

84 ms

目录

LCP 04：覆盖（★★）

题目

分析

解答