NeetCode #734LC-1155Medium2-D Dynamic Programming
← Back to All Problems#734 · #1155 · Number of Dice Rolls With Target Sum(掷骰子等于目标和的方法数)
📌 Problem Statement & Constraints
You roll
n dice, each with k faces numbered 1 to k. Return the number of ways the face-up numbers can sum to target, modulo 1e9+7. Constraints: 1 <= n, k <= 30, 1 <= target <= 1000.💡 Core Algorithmic Approaches
- Let
dp[i][s]be the number of waysidice can sum tos. The base isdp[0][0] = 1. - The recurrence is
dp[i][s] = sum(dp[i-1][s-f])forffrom 1 tok, i.e. the last die shows some facef. - A naive sum over
kfaces per state is O(n * target * k); a prefix sum over the previous layer turns each state into O(1). - Only the previous layer is needed, so two 1-D arrays replace the full table.
💻 Benchmark Python3 Implementation
class Solution:
def numRollsToTarget(self, n: int, k: int, target: int) -> int:
MOD = 10**9 + 7
dp = [0] * (target + 1)
dp[0] = 1 # zero dice reach sum 0 in exactly one way
for _ in range(n):
nxt = [0] * (target + 1)
# prefix[s] = sum of dp[0..s-1]
pre = [0] * (target + 2)
for s in range(target + 1):
pre[s + 1] = (pre[s] + dp[s]) % MOD
for s in range(1, target + 1):
lo = max(0, s - k)
nxt[s] = (pre[s] - pre[lo]) % MOD # sum of dp[s-k .. s-1]
dp = nxt
return dp[target] % MOD⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n * target): n layers, each doing one prefix pass and O(target) O(1) transitions.
💾 Space Complexity
O(target): two rolling 1-D arrays, no n x target table.
⚠️ Interview Pitfalls & Follow-ups
- Summing the
kface transitions explicitly: that is O(n * target * k); the prefix-sum reformulation is the intended O(n * target). - Forgetting to reduce the prefix difference mod:
pre[s] - pre[lo]can be negative in Python, so wrap it in% MOD. - Leaving
dp[0] = 1on later layers: after at least one die, sum 0 is unreachable, sonxt[0]must stay 0 (the loop starting ats = 1guarantees this). - Initialising
dpas all ones: onlydp[0]is 1; every other sum needs a die to reach it.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.