Pythonでn個のダイスを投げることができる方法の数を数えるプログラム

数n、面の数、および合計値があるとすると、合計を取得するために、それぞれの面でn個のサイコロを投げることができる方法の数を見つける必要があります。答えが非常に大きい場合、結果は10 ** 9+7です。

したがって、入力がn =2面=6合計=8のようである場合、2つの6面サイコロで8を作成する5つの方法があるため、出力は5になります：（2と6）、（6と2） 、（3と5）、（5と3）、（4と4）。

これを解決するには、次の手順に従います-

• m：=10 ^ 9 + 7

• dp：=サイズのリスト（合計+ 1）次に0を入力

• 範囲1から最小の顔の場合、各ステップで合計+1ずつ更新します

  • dp [face]：=1

• 0からn-2の範囲のiの場合、実行

  • 合計が0の範囲のjについては、1ずつ減らします。

  • dp [j]：=j --f> =1

    の場合、範囲1から面+1までのfのすべてのdp [j--f]の合計

• dpmodmの最後の要素を返す

理解を深めるために、次の実装を見てみましょう-

例

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