算法-【题解 | 分组背包】掷骰子等于目标和的方法数

掷骰子等于目标和的方法数

力扣：1155. 掷骰子等于目标和的方法数

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

解题思路

我们将每个骰子看作一个组，每个组有k个物品（骰子的面数），每个物品的价值（面数）都不同。我们的目标是从这些组中选择一些物品，使得它们的总价值等于目标值target。

也就是说，"背包"是目标总和target，"物品"是骰子的面数1~k，"组"是这n个骰子。我们需要从每个组（骰子）中选择一些物品（面数），使得它们的总价值（总和）等于背包的容量（目标总和）。

我们定义状态 f[i][j] 表示使用前 i 个骰子得到总和为 j 的方式数量。

状态转移方程为 f[i][j] = (f[i][j] + f[i - 1][j - x]) % mod ，也就是说，对于每个组（骰子）i，我们可以选择或不选择这个组的物品（面数）x，如果我们选择了这个物品，那么我们需要从 f[i - 1][j - x] 转移到 f[i][j]（使用一个骰子，总和增加了x）。

参考代码如下：

class Solution {
    public int numRollsToTarget(int n, int k, int target) {
        final int mod = (int) 1e9 + 7;
        int[][] f = new int[n + 1][target + 1];
        f[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= Math.min(target, i * k); ++j) {
                for (int x = 1; x <= Math.min(j, k); ++x) {
                    f[i][j] = (f[i][j] + f[i - 1][j - x]) % mod;
                }
            }
        }
        return f[n][target];
    }
}