[力扣杯]4. 覆盖

[JalanJiang]

• 原题链接：4. 覆盖
• 题解链接：

---

• 输出题解
• 时间复杂度
• 是否最优解

[JalanJiang]

dp + 状态转移

class Solution:
    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:
        # broken 记录
        broken_map = dict()
        for b in broken:
            if b[0] not in broken_map:
                broken_map[b[0]] = dict()
            broken_map[b[0]][b[1]] = True
            
        """
        是坏格子
        """
        def is_broken(a, b):
            if a in broken_map and b in broken_map[a]:
                return True
            else:
                return False
            
        """
        获取下一个状态
        put: 0-不放，1-横放，2-竖放，3-坏格子
        """
        def next_state(state, put):
            # 去除高位
            state = ~(1 << (m - 1)) & state
            
            if put == 0:
                # 不放牌
                return state << 1
            elif put == 1:
                # 横着放
                return ((state | 1) << 1) | 1
            elif put == 2:
                # 竖着放
                return (state << 1) | 1
            else:
                # 坏格子
                return (state << 1) | 1
            
        # 创建 dp
        dp = [-1] * (1 << m)
        dp[(1 << m) - 1] = 0 # 全 1 的置 0
        
        for i in range(n):
            for j in range(m):
                next_dp = [-1] * (1 << m)
                # 遍历所有状态
                for state in range(1 << m):
                    # 非法状态
                    if dp[state] == -1:
                        continue
                    
                    if is_broken(i, j):
                        # 是坏格子
                        next_dp[next_state(state, 3)] = max(next_dp[next_state(state, 3)], dp[state]) # 是从 dp 转义还是保持现状
                        continue
                       
                    # 不放
                    next_dp[next_state(state, 0)] = max(next_dp[next_state(state, 0)], dp[state])
                    
                    # 可以竖放
                    if i != 0 and (1 << (m - 1)) & state == 0:
                        next_dp[next_state(state, 2)] = max(next_dp[next_state(state, 2)], dp[state] + 1)
                    
                    # 可以横放
                    if j != 0 and 1 & state == 0:
                        next_dp[next_state(state, 1)] = max(next_dp[next_state(state, 1)], dp[state] + 1)
                
                dp = next_dp
                        
        return max(dp)