⚡Flashcard Drill➔
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

  1. Let dp[i][s] be the number of ways i dice can sum to s. The base is dp[0][0] = 1.
  2. The recurrence is dp[i][s] = sum(dp[i-1][s-f]) for f from 1 to k, i.e. the last die shows some face f.
  3. A naive sum over k faces per state is O(n * target * k); a prefix sum over the previous layer turns each state into O(1).
  4. 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 k face 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] = 1 on later layers: after at least one die, sum 0 is unreachable, so nxt[0] must stay 0 (the loop starting at s = 1 guarantees this).
  • Initialising dp as all ones: only dp[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.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems