पायथन में k बैग की संख्या में n कैंडीज की संख्या वितरित करने के तरीकों की संख्या की गणना करने का कार्यक्रम

मान लीजिए, कैंडीज और k बैग की संख्या n है जिसमें कैंडीज डालनी हैं। हमें कैंडीज को वितरित करने के संभावित तरीकों की संख्या का पता लगाना होगा ताकि प्रत्येक बैग में कम से कम एक कैंडी हो। इस परिदृश्य में प्रत्येक कैंडी अद्वितीय है, इसलिए हमें कैंडीज को बैग में वितरित करने के सभी संभावित तरीकों को गिनना होगा।

इसलिए, यदि इनपुट n =3, k =2 जैसा है, तो आउटपुट 3 होगा।

कैंडीज को इस तरह से रखा जा सकता है -

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• dp :=आकार n x n का एक मैट्रिक्स मान 1 के साथ आरंभ किया गया

• c के लिए 2 से n की सीमा में, करें

  • बी के लिए श्रेणी 1 से न्यूनतम (सी, के) में, करें

    • डीपी [सी, बी]:=डीपी [सी -1, बी -1] + डीपी [सी -1, बी] * (बी + 1)

• वापसी डीपी [एन -1, के -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