LeetCode 1155. Number of Dice Rolls With Target Sum

[Woodyiiiiiii]

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:

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.

---

题目大意是有d个骰子，每个骰子有f个面(1, 2, ..., f)，求投完d个骰子后所有朝上的面的数字之和等于target值的所有方法。

创建二维dp数组，d个行，target+1个列，dp[i][j]的含义是投了i+1个骰子数字之和为j的所有方法。

状态转移函数是dp[i][j] = dp[i - 1][j - 0 ] + dp[i - 1][j - 1] + dp[i - 1][j - 2] + ... + dp[i - 1][j - f]，表示dp[i][j]的值由投完前i个骰子的方法数加上第i+1投了的数的方法之和，举例来说，dp[1][7] = dp[0][7] + dp[0][6] + ... + dp[0][1]。

class Solution {
    public int numRollsToTarget(int d, int f, int target) {
        final int mod = 1000000007;
        int[][] dp = new int[d + 1][target + 1];
        dp[0][0] = 1;
        
        for (int i = 1; i <= d; ++i) {
            for (int j = 1; j <= target; ++j) {
                for (int k = 1; k <= f && j - k >= 0; ++k) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod;
                }
            }
        }
        
        return dp[d][target];
    }
}

还有第二种解法，原理都是一样的，但其运行时间比第一种解法少了一半。这种解法是在第二个循环分为了f组。

class Solution {
    public int numRollsToTarget(int d, int f, int target) {
        final int mod = 1000000007;
        int[][] dp = new int[d + 1][target + 1];
        dp[0][0]  =1;
        
        for (int i = 1; i <= d; ++i) {
            for (int j = 1; j <= f; ++j) {
                for (int k = j; k <= target; ++k) {
                    dp[i][k] = (dp[i][k] + dp[i - 1][k - j]) % mod;
                }
            }
        }
        
        return dp[d][target];
    }
}

---

参考资料:

1. LeetCode原题
2. https://www.acwing.com/solution/LeetCode/content/3717/