मान लीजिए कि हमारे पास एक संख्या n, फलकों की संख्या और कुल मान है, तो हमें कुल प्राप्त करने के लिए n पासों को प्रत्येक फलकों के साथ फेंकने के तरीकों की संख्या ज्ञात करनी होगी। अगर उत्तर बहुत बड़ा मॉड है तो परिणाम 10**9 + 7.
इसलिए, यदि इनपुट n =2 चेहरे =6 कुल =8 जैसा है, तो आउटपुट 5 होगा, क्योंकि 2 6-चेहरे वाले पासा के साथ 8 बनाने के 5 तरीके हैं:(2 और 6), (6 और 2) , (3 और 5), (5 और 3), (4 और 4)।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
मी :=10^9 + 7
-
dp:=आकार की एक सूची (कुल + 1) फिर 0 से भरें
-
1 से लेकर न्यूनतम चेहरों तक के चेहरे के लिए, प्रत्येक चरण में कुल + 1 से अपडेट करें, करें
-
डीपी [चेहरा]:=1
-
-
मेरे लिए 0 से n - 2 की सीमा में, करें
-
j के लिए कुल 0 की सीमा में, 1 से घटाएं, करें
-
dp[j] :=f के लिए सभी dp[j - f] का योग 1 से लेकर फलकों तक + 1 जब j - f>=1
-
-
dp mod m का अंतिम तत्व लौटाएं
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
class Solution: def solve(self, n, faces, total): m = 10 ** 9 + 7 dp = [0] * (total + 1) for face in range(1, min(faces, total) + 1): dp[face] = 1 for i in range(n - 1): for j in range(total, 0, -1): dp[j] = sum(dp[j - f] for f in range(1, faces + 1) if j - f >= 1) return dp[-1] % m ob = Solution() n = 2 faces = 6 total = 8 print(ob.solve(n, faces, total))
इनपुट
2,6,8
आउटपुट
5