LeetCode 1155: Number of Dice Rolls With Target Sum (Knapsack-style DP)
LeetCode 1155DPCombinatoricsModuloToday we solve LeetCode 1155 - Number of Dice Rolls With Target Sum.
Source: https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/
English
Problem Summary
Given n dice, each with faces 1..k, count how many ways to roll total sum exactly target.
Return the count modulo 1e9 + 7.
Key Insight
This is a layered DP. Let dp[s] be ways to reach sum s after processing current number of dice.
For each new die, build next by trying face values 1..k.
State Transition
If previous layer has dp[s], then for each face f with s + f <= target:
next[s + f] += dp[s] (mod 1e9 + 7).
Algorithm
1) Initialize dp[0] = 1 (0 dice, sum 0).
2) Repeat n rounds, each round builds a fresh next array.
3) Enumerate all reachable sums and all face values.
4) Move to next layer.
5) Answer is dp[target].
Complexity Analysis
Time: O(n * target * k).
Space: O(target) using rolling arrays.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
private static final int MOD = 1_000_000_007;
public int numRollsToTarget(int n, int k, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int dice = 1; dice <= n; dice++) {
int[] next = new int[target + 1];
for (int s = 0; s <= target; s++) {
if (dp[s] == 0) continue;
for (int f = 1; f <= k && s + f <= target; f++) {
next[s + f] = (next[s + f] + dp[s]) % MOD;
}
}
dp = next;
}
return dp[target];
}
}func numRollsToTarget(n int, k int, target int) int {
const mod int = 1_000_000_007
dp := make([]int, target+1)
dp[0] = 1
for dice := 1; dice <= n; dice++ {
next := make([]int, target+1)
for s := 0; s <= target; s++ {
if dp[s] == 0 {
continue
}
for f := 1; f <= k && s+f <= target; f++ {
next[s+f] = (next[s+f] + dp[s]) % mod
}
}
dp = next
}
return dp[target]
}class Solution {
public:
int numRollsToTarget(int n, int k, int target) {
const int MOD = 1'000'000'007;
vector<int> dp(target + 1, 0);
dp[0] = 1;
for (int dice = 1; dice <= n; ++dice) {
vector<int> next(target + 1, 0);
for (int s = 0; s <= target; ++s) {
if (dp[s] == 0) continue;
for (int f = 1; f <= k && s + f <= target; ++f) {
next[s + f] = (next[s + f] + dp[s]) % MOD;
}
}
dp.swap(next);
}
return dp[target];
}
};class Solution:
def numRollsToTarget(self, n: int, k: int, target: int) -> int:
mod = 1_000_000_007
dp = [0] * (target + 1)
dp[0] = 1
for _ in range(n):
nxt = [0] * (target + 1)
for s, cnt in enumerate(dp):
if cnt == 0:
continue
for f in range(1, k + 1):
ns = s + f
if ns > target:
break
nxt[ns] = (nxt[ns] + cnt) % mod
dp = nxt
return dp[target]var numRollsToTarget = function(n, k, target) {
const MOD = 1000000007;
let dp = new Array(target + 1).fill(0);
dp[0] = 1;
for (let dice = 1; dice <= n; dice++) {
const next = new Array(target + 1).fill(0);
for (let s = 0; s <= target; s++) {
if (dp[s] === 0) continue;
for (let f = 1; f <= k && s + f <= target; f++) {
next[s + f] = (next[s + f] + dp[s]) % MOD;
}
}
dp = next;
}
return dp[target];
};中文
题目概述
给定 n 个骰子，每个骰子点数范围是 1..k，问恰好掷出和为 target 的方案数。
结果对 1e9 + 7 取模。
核心思路
这是分层动态规划。设 dp[s] 表示“当前处理到某一层骰子时，得到和为 s 的方案数”。
每加入一个新骰子，就从旧数组转移到新数组。
状态转移
若旧层中 dp[s] 已知，则遍历点数 f=1..k 且 s+f<=target：
next[s + f] += dp[s]（取模）。
算法步骤
1）初始化 dp[0] = 1，表示 0 个骰子组成和 0 的方式有 1 种。
2）循环 n 轮，每轮创建新的 next 数组。
3）枚举所有可达和 s 与点数 f 完成转移。
4）本轮结束后令 dp = next。
5）最终返回 dp[target]。
复杂度分析
时间复杂度：O(n * target * k)。
空间复杂度：O(target)（滚动数组）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
private static final int MOD = 1_000_000_007;
public int numRollsToTarget(int n, int k, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int dice = 1; dice <= n; dice++) {
int[] next = new int[target + 1];
for (int s = 0; s <= target; s++) {
if (dp[s] == 0) continue;
for (int f = 1; f <= k && s + f <= target; f++) {
next[s + f] = (next[s + f] + dp[s]) % MOD;
}
}
dp = next;
}
return dp[target];
}
}func numRollsToTarget(n int, k int, target int) int {
const mod int = 1_000_000_007
dp := make([]int, target+1)
dp[0] = 1
for dice := 1; dice <= n; dice++ {
next := make([]int, target+1)
for s := 0; s <= target; s++ {
if dp[s] == 0 {
continue
}
for f := 1; f <= k && s+f <= target; f++ {
next[s+f] = (next[s+f] + dp[s]) % mod
}
}
dp = next
}
return dp[target]
}class Solution {
public:
int numRollsToTarget(int n, int k, int target) {
const int MOD = 1'000'000'007;
vector<int> dp(target + 1, 0);
dp[0] = 1;
for (int dice = 1; dice <= n; ++dice) {
vector<int> next(target + 1, 0);
for (int s = 0; s <= target; ++s) {
if (dp[s] == 0) continue;
for (int f = 1; f <= k && s + f <= target; ++f) {
next[s + f] = (next[s + f] + dp[s]) % MOD;
}
}
dp.swap(next);
}
return dp[target];
}
};class Solution:
def numRollsToTarget(self, n: int, k: int, target: int) -> int:
mod = 1_000_000_007
dp = [0] * (target + 1)
dp[0] = 1
for _ in range(n):
nxt = [0] * (target + 1)
for s, cnt in enumerate(dp):
if cnt == 0:
continue
for f in range(1, k + 1):
ns = s + f
if ns > target:
break
nxt[ns] = (nxt[ns] + cnt) % mod
dp = nxt
return dp[target]var numRollsToTarget = function(n, k, target) {
const MOD = 1000000007;
let dp = new Array(target + 1).fill(0);
dp[0] = 1;
for (let dice = 1; dice <= n; dice++) {
const next = new Array(target + 1).fill(0);
for (let s = 0; s <= target; s++) {
if (dp[s] === 0) continue;
for (let f = 1; f <= k && s + f <= target; f++) {
next[s + f] = (next[s + f] + dp[s]) % MOD;
}
}
dp = next;
}
return dp[target];
};
Comments