Chương trình đếm số lượng hình gạch ngang có thể được tạo từ tập hợp các viên gạch bằng Python

Giả sử chúng ta có một danh sách các số được gọi là gạch và hai giá trị khác là chiều rộng và chiều cao. Mỗi phần tử trong gạch [i] đại diện cho một viên gạch có chiều dài là các viên gạch [i] đơn vị và chiều rộng là 1 đơn vị. Chúng ta phải tìm số cách xếp các viên gạch sao cho chúng ta có được đầy đủ bố cục của các viên gạch với chiều rộng và chiều cao đã cho. Chúng ta có thể tái sử dụng các viên gạch nhưng chỉ có thể đặt theo chiều ngang.

Vì vậy, nếu đầu vào giống như gạch =[2, 1] width =3 height =2, thì đầu ra sẽ là 9 vì -

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• w:=một danh sách có kích thước bằng chiều rộng và chèn 1 ở vị trí đầu tiên, các phần còn lại là 0
• đối với tôi trong phạm vi từ 0 đến chiều rộng, thực hiện
  • nếu w [i] khác 0, thì
    • đối với mỗi x trong các khối hình, hãy thực hiện
      • nếu i + x <=width, thì
        • w [i + x]:=w [i + x] + w [i]
• trả về w [width] ^ height

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

bricks = [2, 1]
width = 3
height = 2
print(solve(bricks, width, height))

Đầu vào

[2, 1], 3, 2

Đầu ra

9