You have d dice, and each die has f faces numbered 1, 2, ..., f.

Return the number of possible ways (out of fd total ways) modulo 10^9 + 7 to roll the dice so the sum of the face up numbers equals target.

Example 1:

1
2
3
4
Input: d = 1, f = 6, target = 3
Output: 1
Explanation: 
You throw one die with 6 faces.  There is only one way to get a sum of 3.

Example 2:

1
2
3
4
5
Input: d = 2, f = 6, target = 7
Output: 6
Explanation: 
You throw two dice, each with 6 faces.  There are 6 ways to get a sum of 7:
1+6, 2+5, 3+4, 4+3, 5+2, 6+1.

Example 3:

1
2
3
4
Input: d = 2, f = 5, target = 10
Output: 1
Explanation: 
You throw two dice, each with 5 faces.  There is only one way to get a sum of 10: 5+5.

Example 4:

1
2
3
4
Input: d = 1, f = 2, target = 3
Output: 0
Explanation: 
You throw one die with 2 faces.  There is no way to get a sum of 3.

Example 5:

1
2
3
4
Input: d = 30, f = 30, target = 500
Output: 222616187
Explanation: 
The answer must be returned modulo 10^9 + 7.

Constraints:

  • 1 <= d, f <= 30
  • 1 <= target <= 1000

基本思路是使用动态规划，有n个骰子投出m点的可能数量为sum(n-1个骰子投出m-1的数量, n-1个骰子投出m-2的数量,..., n-1个骰子投出m-f的数量)。对于每一个d都要遍历一遍f个点，每一次遍历中要再遍历一次d-1时的f个点所以最佳时间复杂度应为O(df^2)，在我的实现中因为不知道d-1时的可能点数的起始位置所以实际遍历了所有d*f个可能，实际复杂度为O(d^2f^2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    int MOD = pow(10, 9) + 7;
public:
    int numRollsToTarget(int d, int f, int target) {
        if (target > d * f)
            return 0;
        vector<int> dp1(d * f + 1, 0), dp2(d * f + 1, 0);
        for (int i = 1; i <= f; i++) {
            dp1[i] = 1;
        }

        for (int i = 2; i <= d; i++) {
            for (int j = 1; j < dp1.size(); j++) {
                if (dp1[j] == 0)
                    continue;
                for (int k = 1; k <= f; k++) {
                    dp2[k + j] += dp1[j] % MOD;
                    dp2[k + j] %= MOD;
                }
            }
            swap(dp1, dp2);
            dp2.assign(d * f + 1, 0);
        }

        return dp1[target];
    }
};