โปรแกรมนับจำนวนรูปแบบการวางอิฐแนวนอนจากชุดอิฐใน Python

สมมติว่าเรามีรายการตัวเลขชื่อ bricks และค่าอีกสองค่า width และ height แต่ละสมาชิก bricks[i] แสดงอิฐที่มีความยาว bricks[i] หน่วย และความกว้าง 1 หน่วย เราต้องหาจำนวนวิธีการวางอิฐให้ได้การจัดวางเต็มรูปแบบตาม width และ height ที่กำหนด สามารถนำอิฐมาใช้ซ้ำได้ แต่วางได้เฉพาะแนวนอนเท่านั้น

เช่น ถ้าอินพุตคือ bricks = [2, 1], width = 3, height = 2 ผลลัพธ์จะเป็น 9

ขั้นตอนการแก้ปัญหา

1. w := รายการขนาด width ใส่ 1 ตำแหน่งแรก ที่เหลือ 0
2. สำหรับ i ในช่วง 0 ถึง width:
   • ถ้า w[i] ไม่เป็นศูนย์:
     • สำหรับแต่ละ x ใน bricks:
       • ถ้า i + x <= width ให้ w[i + x] := w[i + x] + w[i]
3. คืนค่า w[width]^height

ตัวอย่างการใช้งาน

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))

อินพุต

[2, 1], 3, 2

เอาต์พุต

9