LeetCode1155-掷骰子的N种方法

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/

中文链接：https://leetcode-cn.com/problems/number-of-dice-rolls-with-target-sum/

题目详述

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

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

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

示例 1：

1
2
输入：d = 1, f = 6, target = 3
输出：1

示例 2：

1
2
输入：d = 2, f = 6, target = 7
输出：6

示例 3：

1
2
输入：d = 2, f = 5, target = 10
输出：1

示例 4：

1
2
输入：d = 1, f = 2, target = 3
输出：0

示例 5：

1
2
输入：d = 30, f = 30, target = 500
输出：222616187

提示：

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

题目详解

  • 典型的动态规划。
  • 设 f(i, j) 表示 i 个骰子掷出的总点数为 target 的组合个数。
  • 则 f(i, j) = f(i - 1, j - 1) + f(i - 1, j - 2) + ... + f(i - 1, j - k)。
  • 初始状态 f(0, 0) = 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class LeetCode_01155 {

    public int numRollsToTarget(int d, int f, int target) {
        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 && k <= j; ++k) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % 1000000007;
                }
            }
        }
        return dp[d][target];
    }
}
  • 可以对上面的代码进行剪枝优化，当 j 大于当前所有骰子的最大和，不可能满足条件，可以直接跳过。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class LeetCode_01155 {

    public int numRollsToTarget(int d, int f, int target) {
        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) {
                // j 大于当前所有骰子的最大和，不可能满足条件
                if (j > i * f) {
                    break;
                }
                for (int k = 1; k <= f && k <= j; ++k) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % 1000000007;
                }
            }
        }
        return dp[d][target];
    }
}
  • 对于 i 而言，只会用到上一层 i - 1 的信息，可以压缩空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class LeetCode_01155 {

    public int numRollsToTarget(int d, int f, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= d; ++i) {
            int[] next = new int[target + 1];
            for (int j = 1; j <= target; ++j) {
                // j 大于当前所有骰子的最大和，不可能满足条件
                if (j > i * f) {
                    break;
                }
                for (int k = 1; k <= f && k <= j; ++k) {
                    next[j] = (next[j] + dp[j - k]) % 1000000007;
                }
            }
            dp = next;
        }
        return dp[target];
    }
}