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

मान लीजिए, 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 से min(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