1155. 掷骰子等于目标和的方法数(1654)

这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。

给定三个整数 n、k 和 target，请返回投掷骰子的所有可能得到的结果（共有 k^n 种方式），使得骰子面朝上的数字总和等于 target。

由于答案可能很大，你需要对 10^9 + 7 取模。

示例 1：

1
2
3
4
输入：n = 1, k = 6, target = 3
输出：1
解释：你掷了一个有 6 个面的骰子。
得到总和为 3 的结果的方式只有一种。

示例 2：

1
2
3
4
输入：n = 2, k = 6, target = 7
输出：6
解释：你掷了两个骰子，每个骰子有 6 个面。
有 6 种方式得到总和为 7 的结果: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1。

示例 3：

1
2
3
输入：n = 30, k = 30, target = 500
输出：222616187
解释：返回的结果必须对 109 + 7 取模。

提示：

  • 1 <= n, k <= 30
  • 1 <= target <= 1000

思路：多重背包（背包恰好装capacity，求方案数）

多重背包是看成 n 种物品，每种物品的大小都是 1，每种物品至少选 1 个，至多选 k 个，计算组成大小为 target 的方案数。

  • 物品重量 = 1，至少1个，至多k个
  • 物品价值 = null
  • 背包容量 = target

这题也可以看作是分组背包，分组背包是看成 n 组，每组内有大小分别为 1,2,…,k 的物品，计算每组恰好选一个物品，组成大小为 target 的方案数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    int mod = (int)1e9+7;
    public int numRollsToTarget(int n, int k, int target) {
        // dp[i][j]: 用i个骰子获得数字总和为j的方案数
        int dp[][] = new int[n+1][target+1];
        dp[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= target; j++) {
                for (int l = 1; l <= Math.min(k, j); l++) {  // 遍历当前骰子的所有可能数字
                    dp[i+1][j] = (dp[i+1][j] + dp[i][j-l]) % mod;
                }
            }
        }
        return dp[n][target];
    }
}