1352. Product of the Last K Numbers

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 109 + 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.

Constraints:

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

这道题题说是给了d个骰子，每个骰子有f个面，现在给了一个目标值 target，问同时投出这d个骰子，共有多少种组成目标值的不同组合，结果对超大数字 1e9+7 取余。这道题其实跟之前的 Coin Change 2 硬币找零系列很类似，只不过这里相当于确定了硬币的总数一定要为d。万变不离其宗，还是用动态规划 Dynamic Programming 来做，首先来考虑 dp 数组该如何定义，根据硬币找零系列的启发，目标值本身肯定是占一个维度的，因为这个是要求的东西，另外就是当前骰子的个数也是要考虑的因素，所以这里使用一个二维的 dp 数组，其中 dp[i][j] 表示使用i个骰子组成目标值为j的所有组合个数，大小为 d+1 by target+1，并初始化 dp[0][0] 为1。接下来就是找状态转移方程了，当前某个状态 dp[i][k] 跟什么相关呢，其表示为使用i个骰子组成目标值k，那么拿最后一个骰子的情况分析，其可能会投出 [1, f] 中的任意一个数字j，那么之前的目标值就是 k-j，且用了 i-1 个骰子，其 dp 值就是 dp[i-1][k-j]，当前投出的点数可以跟之前所有的情况组成一种新的组合，所以当前的 dp[i][k] 就要加上 dp[i-1][k-j]，那么状态转移方程就呼之欲出了：

dp[i][k] = (dp[i][k] + dp[i - 1][k - j]) % M;

其中i的范围是 [1, d]，j的范围是 [1, f]，k的范围是 [j, target]，总共三个 for 循环嵌套在一起，最终返回 dp[d][target] 即可，参见代码如下：

解法一：

class Solution {
public:
    int numRollsToTarget(int d, int f, int target) {
        int M = 1e9 + 7;
        vector<vector<int>> dp(d + 1, vector<int>(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]) % M;
                }
            }
        }
        return dp[d][target];
    }
};

我们可以进行空间上的优化，由于当前使用i个骰子的状态值依赖于使用 i-1 个骰子的状态，所以没必要保存所有的骰子个数的 dp 值，可以在遍历i的时候，新建一个临时的数组t，来保存使用i个骰子的 dp 值，并在最后交换 dp 和 t 即可，参见代码如下：

解法二：

class Solution {
public:
    int numRollsToTarget(int d, int f, int target) {
        int M = 1e9 + 7;
        vector<int> dp(target + 1);
        dp[0] = 1;
        for (int i = 1; i <= d; ++i) {
            vector<int> t(target + 1);
            for (int j = 1; j <= f; ++j) {
                for (int k = j; k <= target; ++k) {
                    t[k] = (t[k] + dp[k - j]) % M;
                }
            }
            swap(dp, t);
        }
        return dp[target];
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1155

类似题目：

Coin Change 2

Equal Sum Arrays With Minimum Number of Operations

参考资料：

https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/

https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/discuss/355841/Java-Memo-DFS

https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/discuss/355940/C%2B%2B-Coin-Change-2

LeetCode All in One 题目讲解汇总(持续更新中…)

---

转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com