ধরুন, সেখানে n সংখ্যক ক্যান্ডি এবং k ব্যাগ রয়েছে যেখানে ক্যান্ডিগুলি রাখতে হবে। প্রতিটি ব্যাগে অন্তত একটি মিছরি ধারণ করার জন্য ক্যান্ডিগুলি বিতরণ করা যেতে পারে এমন সম্ভাব্য উপায়গুলির সংখ্যা আমাদের খুঁজে বের করতে হবে। এই পরিস্থিতিতে প্রতিটি মিছরি অনন্য, তাই আমাদের সমস্ত সম্ভাব্য উপায়গুলি গণনা করতে হবে যে ক্যান্ডিগুলি ব্যাগে বিতরণ করা যেতে পারে৷
সুতরাং, যদি ইনপুট n =3, k =2 এর মত হয়, তাহলে আউটপুট হবে 3।
ক্যান্ডি এইভাবে রাখা যেতে পারে -
(1, 2), (3) (1) , (2, 3) (2), (1, 3)
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
dp :=মান 1
সহ n x n আকারের একটি ম্যাট্রিক্স শুরু -
2 থেকে n পরিসরে c এর জন্য, করুন
-
1 থেকে সর্বনিম্ন (c, k) পরিসরে b এর জন্য, করুন
-
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
