Chương trình đếm số mẫu gạch ngang từ tập gạch cho trước Python

Cho danh sách bricks (độ dài từng viên gạch, chiều rộng = 1), chiều rộng width và cao height. Đếm số cách xếp gạch ngang đầy khung width x height (có thể tái sử dụng gạch).

Ví dụ: bricks=[2,1], width=3, height=2 → 9 cách.

Giải thuật (Quy hoạch động)

1. w[i] = số cách tạo độ rộng i cho một hàng
2. Khởi tạo w[0]=1, các vị trí khác = 0
3. Duyệt i từ 0 đến width: nếu w[i]>0, thử thêm mỗi loại gạch x → w[i+x] += w[i]
4. Số cách cho toàn bộ tường = w[width]^height

Ví dụ triển khai

def solve(bricks, width, height):
    w = [1] + [0] * width
    for i in range(width):
        if w[i]:
            for x in bricks:
                if i + x <= width:
                    w[i + x] += w[i]
    return w[width] ** height

print(solve([2, 1], 3, 2))

Đầu vào

[2, 1], 3, 2

Đầu ra

9