掷骰子等于目标和的方法数【LC1155】
这里有
n个一样的骰子，每个骰子上都有k个面，分别标号为1到k。给定三个整数
n,k和target，返回可能的方式(从总共kn种方式中)滚动骰子的数量，使正面朝上的数字之和等于target。答案可能很大，你需要对
109 + 7取模 。
第一眼很像背包
记忆化
- 思路
class Solution { public static final int MOD = (int)(1e9 + 7); int[][] dp; int k; public int numRollsToTarget(int n, int k, int target) { // 选择n个数，值为1-k，和为target的方案数 if (n * k < target) return 0; this.k = k; this.dp = new int[n + 1][target + 1]; for (int i = 1; i <= n; i++){ Arrays.fill(dp[i], -1); } dp[0][0] = 1; return dfs(n, target); } public int dfs(int n, int target){ if (dp[n][target] != -1) return dp[n][target]; int res = 0; for (int i = 1; i <= Math.min(target, k); i++){ res = (res + dfs(n - 1, target - i)) % MOD; } dp[n][target] = res; return res; } }
- 优化：每个数至少取1， 因此可以将target减少n，每个数的范围减小1
递推
- 实现
class Solution { public static final int MOD = (int)(1e9 + 7); public int numRollsToTarget(int n, int k, int target) { // 选择n个数，值为1-k，和为target的方案数 if (n * k < target) return 0; int[][] dp = new int[n + 1][target + 1]; dp[0][0] = 1; for (int i = 1; i <= n; i++){ for (int j = 1; j <= Math.min(k, target); j++){ for (int v = j; v <= target; v++){ dp[i][v] = (dp[i][v] + dp[i - 1][v - j]) % MOD; } } } return dp[n][target]; } }
