1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution:
def __init__(self):
self.dp = [[0]*1024 for _ in range(101)]
def dfs_h(self, h, i, ids):
if h == 0:
return 1
if self.dp[h][i] == 0:
for j in ids[i]:
self.dp[h][i] = (self.dp[h][i] + self.dfs_h(h - 1, j, ids)) % 1000000007
return self.dp[h][i]
def dfs_w(self, w, width, bricks, mask, masks):
if w == width:
masks.append(mask)
else:
if w:
mask += (1 << (w - 1))
for b in bricks:
if w + b <= width:
self.dfs_w(w + b, width, bricks, mask, masks)
return masks
def buildWall(self, height: int, width: int, bricks: List[int]) -> int:
masks = self.dfs_w(0, width, bricks, 0, [])
ids = [[] for _ in range(len(masks) + 1)]
for i in range(len(masks)):
for j in range(len(masks)):
if i == 0:
ids[0].append(j + 1)
if (masks[i] & masks[j]) == 0:
ids[i + 1].append(j + 1)
return self.dfs_h(height, 0, ids)
|