如何制作班级网站,深圳居家办公最新通知,国家企业信用网(江苏),百度关键词收费标准掷骰子等于目标和的方法数 力扣#xff1a;1155. 掷骰子等于目标和的方法数 这里有 n 个一样的骰子#xff0c;每个骰子上都有 k 个面#xff0c;分别标号为 1 到 k 。
给定三个整数 n、k 和 target#xff0c;请返回投掷骰子的所有可能得到的结果#xff08;共有 kn 种方…掷骰子等于目标和的方法数 力扣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 的结果: 16, 25, 34, 43, 52, 61。示例 3
输入n 30, k 30, target 500
输出222616187
解释返回的结果必须对 109 7 取模。提示
1 n, k 301 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];}
}
