Problem statement

https://binarysearch.com/problems/Brick-Layout/

Solution

Use classical knapsack here.

Complexity

It is O(W * n) for time and O(W) for space.

Code

class Solution:
    def solve(self, bricks, W, H):
        n = len(bricks)

        @lru_cache(None)
        def dp(i):
            if i < 0: return 0
            if i == 0: return 1
            return sum(dp(i - x) for x in bricks)

        return dp(W)**H