Chương trình đếm số cách phân phối n số kẹo trong k số túi bằng Python

Giả sử có n số kẹo và k túi đựng kẹo phải bỏ vào đó. Chúng ta phải tìm ra số cách có thể phân phối kẹo sao cho mỗi túi chứa ít nhất một viên kẹo. Mỗi viên kẹo trong trường hợp này là duy nhất, vì vậy chúng tôi phải đếm tất cả các cách có thể để kẹo có thể được phân phối trong các túi.

Vì vậy, nếu đầu vào là n =3, k =2, thì đầu ra sẽ là 3.

Kẹo có thể được đặt theo cách này -

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

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

• dp:=ma trận kích thước n x n được khởi tạo với giá trị 1

• đối với c trong phạm vi 2 đến n, thực hiện

  • đối với b trong phạm vi từ 1 đến tối thiểu của (c, k), thực hiện

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

• trả về dp [n-1, k-1]

Ví dụ

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

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

Đầu vào

3, 2

Đầu ra

3