Pythonでサイコロの出目の合計がターゲットと一致する組み合わせの数を求める

d個のサイコロがあり、それぞれのサイコロには1からfまでの数字が書かれた面があるとします。このとき、出た目の合計がターゲットの値と一致するような振り方（全 fd 通りのうち）の数を、10^9 + 7 で割った余りとして求めます。

例えば、d = 2、f = 6、target = 7 の場合、答えは6になります。6面のサイコロ2つを振って合計が7になる組み合わせは、「1+6」「2+5」「3+4」「4+3」「5+2」「6+1」の6通り存在するためです。

解法のアプローチ

この問題は動的計画法（DP）を使うことで効率的に解けます。手順は以下の通りです。

• m := 10^9 + 7（剰余を取るための定数）を定義する
• d × (t + 1) のサイズのdpテーブルを作成し、すべて0で初期化する
• i を 0 から d − 1 まで繰り返す
  • j を 0 から t まで繰り返す
    • i = 0 の場合：j が 1 以上 f 以下なら dp[i, j] := 1、それ以外は 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 を適用する
• 最後に dp[d − 1][t] mod m を返す

アルゴリズムのポイント

このDPにおいて、dp[i][j] は「i番目までのサイコロを使って合計 j を作る方法の数」を表します。最初のサイコロ（i = 0）については、出目 j が 1 以上 f 以下であればちょうど1通りのみ存在します。2個目以降のサイコロでは、直前の状態に各出目 l（1〜f）を加えることで遷移できるため、dp[i−1][j−l] の総和を計算します。また、答えが巨大な数になるのを防ぐため、毎回 10^9 + 7 の剰余を取っている点も重要なポイントです。

Pythonでの実装例

理解を深めるために、以下の実装例を見てみましょう。

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