โปรแกรมนับจำนวนวิธีในการแจกลูกอม n จำนวน k จำนวนถุงใน Python

สมมติว่ามีขนมจำนวน n ชิ้นและถุง k ถุงที่ต้องใส่ขนมลงไป เราต้องหาจำนวนวิธีที่เป็นไปได้ในการแจกจ่ายขนม เพื่อให้แต่ละถุงมีขนมอย่างน้อยหนึ่งชิ้น ลูกอมทุกตัวในสถานการณ์นี้มีเอกลักษณ์เฉพาะตัว ดังนั้นเราจึงต้องนับวิธีที่เป็นไปได้ทั้งหมดที่แคนดี้สามารถแจกจ่ายในถุงได้

ดังนั้น หากอินพุตเป็น n =3, k =2 เอาต์พุตจะเป็น 3

สามารถใส่ขนมในลักษณะนี้ −

(1, 2), (3)
(1) , (2, 3)
(2), (1, 3)

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• dp :=เมทริกซ์ขนาด n x n เริ่มต้นด้วยค่า 1

• สำหรับ c ในช่วง 2 ถึง n ทำ

  • สำหรับ b ในช่วง 1 ถึงค่าต่ำสุดของ (c, k) ทำ

    • dp[c, b] :=dp[c-1, b-1] + dp[c-1, b] * (b+1)

• กลับ dp[n-1, k-1]

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def solve(n, k):
   dp = [[1] * n for _ in range(n)]
   for c in range(2, n):
      for b in range(1,min(c,k)):
         dp[c][b] = dp[c-1][b-1] + dp[c-1][b] * (b+1)
   return dp[n-1][k-1]

print(solve(3, 2))

อินพุต

3, 2

ผลลัพธ์

3