1155. Number of Dice Rolls With Target Sum

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

💰


微信打赏


Venmo 打赏

×

Help us with donation