# 2184. Number of Ways to Build Sturdy Brick Wall     • Time: $O(n \cdot \texttt{height})$, where n = len(rows)
• Space: $O(n)$
  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 34 35 36 37 38 39 40 41 42 43 44 class Solution { public: int buildWall(int height, int width, vector& bricks) { const int kMod = 1'000'000'007; // Valid rows in bitmask. vector rows; buildRows(width, bricks, 0, rows); const int n = rows.size(); // dp[i] := # of ways to build h height walls with rows[i] in the bottom vector dp(n, 1); // graph[i] := valid neighbors of rows[i]. vector> graph(n); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (!(rows[i] & rows[j])) graph[i].push_back(j); for (int h = 2; h <= height; ++h) { vector newDp(n); for (int i = 0; i < n; ++i) for (const int v : graph[i]) { newDp[i] += dp[v]; newDp[i] %= kMod; } dp = move(newDp); } return accumulate(begin(dp), end(dp), 0L) % kMod; } private: void buildRows(int width, const vector& bricks, int path, vector& rows) { for (const int brick : bricks) if (brick == width) rows.push_back(path); else if (brick < width) { const int newWidth = width - brick; buildRows(newWidth, bricks, path | 1 << newWidth, rows); } } }; 
  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 34 35 36 37 38 39 40 41 42 43 44 45 46 class Solution { public int buildWall(int height, int width, int[] bricks) { final int kMod = 1_000_000_007; // Valid rows in bitmask. List rows = new ArrayList<>(); buildRows(width, bricks, 0, rows); final int n = rows.size(); // dp[i] := # of ways to build h height walls With rows[i] in the bottom long[] dp = new long[n]; // graph[i] := valid neighbors of rows[i]. List[] graph = new List[n]; Arrays.fill(dp, 1); for (int i = 0; i < n; ++i) graph[i] = new ArrayList<>(); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if ((rows.get(i) & rows.get(j)) == 0) graph[i].add(j); for (int h = 2; h <= height; ++h) { long[] newDp = new long[n]; for (int i = 0; i < n; ++i) for (final int v : graph[i]) { newDp[i] += dp[v]; newDp[i] %= kMod; } dp = newDp; } return (int) (Arrays.stream(dp).sum() % kMod); } private void buildRows(int width, int[] bricks, int path, List rows) { for (final int brick : bricks) if (brick == width) rows.add(path); else if (brick < width) { final int newWidth = width - brick; buildRows(newWidth, bricks, path | 1 << newWidth, rows); } } } 
  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 34 35 class Solution: def buildWall(self, height: int, width: int, bricks: List[int]) -> int: kMod = 1_000_000_007 # Valid rows in bitmask. rows = [] self._buildRows(width, bricks, 0, rows) n = len(rows) # dp[i] := # of ways to build h height walls with rows[i] in the bottom dp =  * n # graph[i] := valid neighbors of rows[i]. graph = [[] for _ in range(n)] for i, a in enumerate(rows): for j, b in enumerate(rows): if not a & b: graph[i].append(j) for _ in range(2, height + 1): newDp =  * n for i in range(n): for v in graph[i]: newDp[i] += dp[v] newDp[i] %= kMod dp = newDp return sum(dp) % kMod def _buildRows(self, width: int, bricks: List[int], path: int, rows: List[int]): for brick in bricks: if brick == width: rows.append(path) elif brick < width: newWidth = width - brick self._buildRows(newWidth, bricks, path | 2 << newWidth, rows)