1155. Number of Dice Rolls With Target Sum

[Tcdian]

1155. Number of Dice Rolls With Target Sum

这里有 d 个一样的骰子，每个骰子上都有 f 个面，分别标号为 1, 2, ..., f。

我们约定：掷骰子的得到总点数为各骰子面朝上的数字的总和。

如果需要掷出的总点数为target，请你计算出有多少种不同的组合情况（所有的组合情况总共有 f^d 种），模 10^9 + 7 后返回。

Example 1

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

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

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

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

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

[Tcdian]

Solution ( DP )

• Go Solution

func numRollsToTarget(d int, f int, target int) int {
    const mod = 1e9 + 7;
    dp := make([][]int, d + 1);
    for i := 0; i <= d; i++ {
        dp[i] = make([]int, target + 1);
        if i == 0 {
            dp[0][0] = 1;
            continue;
        }
        for j := 1; j <= target; j++ {
            for k := 1; k <= f && k <= j; k++ {
                dp[i][j] += dp[i - 1][j - k];
            }
            dp[i][j] %= mod;
        }
    }
    return dp[d][target];
}