मान लीजिए हमारे पास d डाइस हैं, और प्रत्येक डाइस में f संख्या में फेसेस हैं जो 1, 2, ..., f से नंबर किए गए हैं। हमें संभावित तरीकों की संख्या ढूंढनी है (कुल f^d तरीकों में से) मॉड्यूलो 10^9 + 7 डाइस को रोल करने के लिए ताकि फेस-अप नंबरों का योग टारगेट के बराबर हो। इसलिए यदि इनपुट d = 2, f = 6, target = 7 है, तो आउटपुट 6 होगा। इसलिए यदि हम प्रत्येक डाइस को 6 फेसेस के साथ फेंकते हैं, तो योग 7 प्राप्त करने के 6 तरीके हैं, जैसे 1 + 6, 2 + 5, 3 + 4, 4 + 3, 5 + 2, 6 + 1।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- m := 1e9 + 7
- d x (t + 1) ऑर्डर का एक टेबल dp बनाएं, और इसे 0 से भरें
- i को 0 से d - 1 तक रेंज में
- j को 0 से t तक रेंज में
- यदि i = 0, तो dp[i, j] := 1 जब j 1 से f की रेंज में हो, अन्यथा 0
- अन्यथा
- l को 1 से f तक रेंज में
- यदि j - l > 0, तो dp[i, j] := dp[i, j] + dp[i - 1, j - l], और dp[i,j] := dp[i, j] mod m
- l को 1 से f तक रेंज में
- j को 0 से t तक रेंज में
- dp[d - 1, t] mod m लौटाएं
उदाहरण (पायथन)
बेहतर समझ पाने के लिए निम्न कार्यान्वयन देखें -
class Solution(object):
def numRollsToTarget(self, d, f, t):
mod = 1000000000+7
dp =[[0 for i in range(t+1)] for j in range(d)]
for i in range(d):
for j in range(t+1):
if i == 0:
dp[i][j] = 1 if j>=1 and j<=f else 0
else:
for l in range(1,f+1):
if j-l>0:
dp[i][j]+=dp[i-1][j-l]
dp[i][j]%=mod
return dp [d-1][t] % mod
ob = Solution()
print(ob.numRollsToTarget(2,6,7))इनपुट
2 6 7
आउटपुट
6