本文正在参加「Python主题月」，详情查看 活动链接
题目描述
这是 LeetCode 上的「1155. 掷骰子的N种方法」，难度为「中等」。
Tag : 「背包问题」、「动态规划」、「分组背包」
这里有 d 个一样的骰子，每个骰子上都有 f 个面，分别标号为 1,2,...,f。
我们约定：掷骰子的得到总点数为各骰子面朝上的数字的总和。
如果需要掷出的总点数为 target，请你计算出有多少种不同的组合情况（所有的组合情况总共有 种），模 后返回。
示例 1：
输入：d = 1, f = 6, target = 3
输出：1
复制代码示例 2：
输入：d = 2, f = 6, target = 7
输出：6
复制代码示例 3：
输入：d = 2, f = 5, target = 10
输出：1
复制代码示例 4：
输入：d = 1, f = 2, target = 3
输出：0
复制代码示例 5：
输入：d = 30, f = 30, target = 500
输出：222616187
复制代码提示：
-
1 <= d, f <= 30
-
1 <= target <= 1000
分组背包
在 分组背包问题 中我们提到，分组背包不仅仅有「组内物品最多选择一个」的情况，还存在「组内物品必须选择一个」的情况。
对于本题，可以将每个骰子看作一个物品组，且每次 必须 从物品组中选择一个物品（所掷得的数值大小视作具体物品）。
这样就把问题转换为：用 个骰子（物品组）进行掷，掷出总和（取得的总价值）为 的方案数。
虽然，我们还没专门讲过「背包问题求方案数」，但基本分析与「背包问题求最大价值」并无本质区别。
我们可以套用「分组背包求最大价值」的状态定义来微调： 表示考虑前 个物品组，凑成价值为 的方案数。
为了方便，我们令物品组的编号从 开始，因此有显而易见的初始化条件 。
代表在不考虑任何物品组的情况下，只有凑成总价值为 的方案数为 ，凑成其他总价值的方案不存在。
不失一般性考虑 该如何转移，也就是考虑第 个物品组有哪些决策。
根据题意，对于第 个物品组而言，可能决策的方案有：
-
第 个骰子的结果为 ，有
-
第 个骰子的结果为 ，有
...
-
第 个骰子的结果为 ，有
则是上述所有可能方案的方案数总和，即有：
朴素二维
Java 代码：
class Solution {
int mod = (int)1e9+7;
public int numRollsToTarget(int n, int m, int t) {
int[][] f = new int[n + 1][t + 1];
f[0][0] = 1;
// 枚举物品组（每个骰子）
for (int i = 1; i <= n; i++) {
// 枚举背包容量（所掷得的总点数）
for (int j = 0; j <= t; j++) {
// 枚举决策（当前骰子所掷得的点数）
for (int k = 1; k <= m; k++) {
if (j >= k) {
f[i][j] = (f[i][j] + f[i-1][j-k]) % mod;
}
}
}
}
return f[n][t];
}
}
复制代码- 时间复杂度：
- 空间复杂度：
滚动数组
根据状态转移方程，我们发现 明确只依赖于 ，且 。
因此我们可以使用之前学过的「滚动数组」，用很机械的方式将空间从 优化至 。
需要注意的是，由于我们直接是在 格子的基础上进行方案数累加，因此在计算 记得手动置零。
Java 代码：
class Solution {
int mod = (int)1e9+7;
public int numRollsToTarget(int n, int m, int t) {
int[][] f = new int[2][t + 1];
f[0][0] = 1;
for (int i = 1; i <= n; i++) {
int a = i & 1, b = (i - 1) & 1;
for (int j = 0; j <= t; j++) {
f[a][j] = 0; // 先手动置零
for (int k = 1; k <= m; k++) {
if (j >= k) {
f[a][j] = (f[a][j] + f[b][j-k]) % mod;
}
}
}
}
return f[n&1][t];
}
}
复制代码- 时间复杂度：
- 空间复杂度：
一维空间优化
更进一步，利用「 明确只依赖于 ，且 」，我们能通过「01 背包」一维空间优化方式：将物品维度取消，调整容量维度遍历顺序为「从大到小」。
Java 代码：
class Solution {
int mod = (int)1e9+7;
public int numRollsToTarget(int n, int m, int t) {
int[] f = new int[t + 1];
f[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = t; j >= 0; j--) {
f[j] = 0;
for (int k = 1; k <= m; k++) {
if (j >= k) {
f[j] = (f[j] + f[j-k]) % mod;
}
}
}
}
return f[t];
}
}
复制代码- 时间复杂度：
- 空间复杂度：
总结
不难发现，不管是「组内物品最多选一件」还是「组内物品必须选一件」。
我们都是直接套用分组背包基本思路「枚举物品组-枚举容量-枚举决策」进行求解。
分组背包的空间优化并不会降低时间复杂度，所以对于分组背包问题，我们可以直接写方便调试的朴素多维版本（在空间可接受的情况下），如果遇到卡空间，再通过机械的方式改为「滚动数组」形式。
另外今天我们使用「分组背包问题求方案数」来作为「分组背包问题求最大价值」的练习题。
可以发现，两者其实并无本质区别，都是套用「背包问题求最大价值」的状态定义来微调。
更多的关于「背包问题求方案数」相关内容，在后面也会继续细讲。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1155 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
