Skip to content

234. Number of Dice Rolls With Target Sum

πŸ”— LeetCode Problem: 1155. Number of Dice Rolls With Target Sum
πŸ“Š Difficulty: Medium
🏷️ Topics: Dynamic Programming, DP - Subsequences, Counting

Problem Statement

You have n dice, and each die has k faces numbered from 1 to k.

Given three integers n, k, and target, return the number of possible ways (out of the k^n total ways) to roll the dice, so the sum of the face-up numbers equals target. Since the answer may be too large, return it modulo 10^9 + 7.

Example 1: 

Input: n = 1, k = 6, target = 3
Output: 1
Explanation: You throw one die with 6 faces.
There is only one way to get a sum of 3.

Example 2: 

Input: n = 2, k = 6, target = 7
Output: 6
Explanation: You throw two dice, each with 6 faces.
There are 6 ways to get a sum of 7: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1.

Example 3: 

Input: n = 30, k = 30, target = 500
Output: 222616187
Explanation: The answer must be returned modulo 10^9 + 7.

Constraints: - 1 <= n, k <= 30 - 1 <= target <= 1000

πŸ” Let's Discover the Pattern Together

Start with Small Examples

Let's not jump to the solution. Let's understand what's really happening by trying small examples:

Example 1: n = 1, k = 6, target = 3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
One die with faces [1, 2, 3, 4, 5, 6]
Want sum = 3

Possibilities:
  Roll 3 β†’ sum = 3 βœ“

Answer: 1 way

Simple! Just roll the target value.

Example 2: n = 2, k = 6, target = 7
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Two dice, each with faces [1, 2, 3, 4, 5, 6]
Want sum = 7

Possibilities:
  Die1 = 1, Die2 = 6 β†’ sum = 7 βœ“
  Die1 = 2, Die2 = 5 β†’ sum = 7 βœ“
  Die1 = 3, Die2 = 4 β†’ sum = 7 βœ“
  Die1 = 4, Die2 = 3 β†’ sum = 7 βœ“
  Die1 = 5, Die2 = 2 β†’ sum = 7 βœ“
  Die1 = 6, Die2 = 1 β†’ sum = 7 βœ“

Answer: 6 ways

Notice: Order matters! (1,6) is different from (6,1)

Example 3: n = 2, k = 6, target = 3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Two dice, want sum = 3

Possibilities:
  Die1 = 1, Die2 = 2 β†’ sum = 3 βœ“
  Die1 = 2, Die2 = 1 β†’ sum = 3 βœ“

Answer: 2 ways

Can't use (1,1) because sum = 2
Can't use (3,0) because die faces are 1-6

Notice the Pattern

Let's think about Example 2 more carefully:

n = 2, k = 6, target = 7

For the FIRST die, what values can we roll?
  - If we roll 1, we need remaining dice to sum to 7-1=6
  - If we roll 2, we need remaining dice to sum to 7-2=5
  - If we roll 3, we need remaining dice to sum to 7-3=4
  - If we roll 4, we need remaining dice to sum to 7-4=3
  - If we roll 5, we need remaining dice to sum to 7-5=2
  - If we roll 6, we need remaining dice to sum to 7-6=1

For each choice on first die, count ways with remaining dice!

This is RECURSIVE thinking! 🎯

The Breakthrough

Let's say we want: count(n dice, target sum)

For the first die, we can roll values 1 to k:
  - Roll 1 β†’ need count(n-1 dice, target-1)
  - Roll 2 β†’ need count(n-1 dice, target-2)
  - Roll 3 β†’ need count(n-1 dice, target-3)
  - ...
  - Roll k β†’ need count(n-1 dice, target-k)

Total ways = sum of all these possibilities!

count(n, target) = Ξ£ count(n-1, target-face) for face in [1..k]

Base cases:
  - If n = 0 and target = 0 β†’ 1 way (used all dice, reached target!)
  - If n = 0 and target > 0 β†’ 0 ways (no dice left, can't reach target)
  - If target < 0 β†’ 0 ways (went below 0, impossible)

This is the RECURSIVE STRUCTURE! πŸ”‘

Let's Trace Example 2

count(2 dice, target=7):

  First die rolls 1:
    Need: count(1 die, target=6)
      Second die rolls 6 β†’ count(0 dice, 0) = 1 βœ“
    Ways: 1

  First die rolls 2:
    Need: count(1 die, target=5)
      Second die rolls 5 β†’ count(0 dice, 0) = 1 βœ“
    Ways: 1

  First die rolls 3:
    Need: count(1 die, target=4)
      Second die rolls 4 β†’ count(0 dice, 0) = 1 βœ“
    Ways: 1

  First die rolls 4:
    Need: count(1 die, target=3)
      Second die rolls 3 β†’ count(0 dice, 0) = 1 βœ“
    Ways: 1

  First die rolls 5:
    Need: count(1 die, target=2)
      Second die rolls 2 β†’ count(0 dice, 0) = 1 βœ“
    Ways: 1

  First die rolls 6:
    Need: count(1 die, target=1)
      Second die rolls 1 β†’ count(0 dice, 0) = 1 βœ“
    Ways: 1

Total: 1 + 1 + 1 + 1 + 1 + 1 = 6 ways βœ“

Perfect match!

πŸ’‘ The AHA Moment - Understanding the Structure

The Recursive Insight

Key observation:
  To count ways with n dice to reach target,
  we need to know:
    - What face do we roll on CURRENT die? (1 to k)
    - How many ways to reach REMAINING target with REMAINING dice?

This creates a natural recursion:
  count(n, target) = Ξ£ count(n-1, target-face) for all valid faces

It's like choosing from multiple options and summing the results!

Does This Remind You of Something?

Think about Coin Change 2 (Problem 231):

Coin Change 2:
  "Count ways to make amount using unlimited coins"
  dp[amount] += dp[amount - coin]
  Each coin can be used multiple times

This problem:
  "Count ways to make target using n dice (k faces each)"
  count(n, target) = Ξ£ count(n-1, target-face)
  Each die used exactly once (bounded by n)

Similarities:
  - Both COUNT ways (not minimize/maximize)
  - Both involve SUM to reach target
  - Both involve CHOICES (faces vs coins)

Differences:
  - This has BOUNDED dice (exactly n)
  - Coin Change has UNLIMITED coins
  - This is 2D state (n, target)
  - Coin Change is 1D state (target)

The State Definition

What information do we need to count ways?

State: (dice_remaining, target_remaining)
  - How many dice left to roll?
  - What target sum do we still need?

With this state, we can make decisions:
  - For each face value (1 to k)
  - Recursively count ways with (n-1, target-face)
  - Sum all possibilities

This gives us our DP structure!

πŸ”΄ Approach 1: Brute Force (Pure Recursion)

πŸ“ Function Definition

Function Signature: 

int numRollsToTarget(int n, int k, int target)

What does this function compute? - Input n: Number of dice remaining to roll - Input k: Number of faces on each die (1 to k) - Input target: Target sum we need to achieve - Output: Number of ways to achieve target sum with n dice

What does the recursive call represent? - count(n, target): Ways to get target sum using n dice - For each face value f (1 to k): - Try rolling f on current die - Recursively count ways with remaining: count(n-1, target-f) - Sum all possibilities

The Recursive Structure: 

count(n, target) = Ξ£ count(n-1, target-face) for face in [1..k]

Base cases:
  - n = 0 and target = 0 β†’ return 1 (success!)
  - n = 0 and target > 0 β†’ return 0 (failed)
  - target < 0 β†’ return 0 (impossible)

Answer: count(n, target) mod 10^9+7

Why this works: 

Every valid way to reach target corresponds to:
  - A sequence of n die rolls
  - Where each roll is between 1 and k
  - And the sum equals target

By trying all face values on first die,
and recursively counting ways with remaining dice,
we enumerate ALL possible sequences!

πŸ’‘ Intuition

Think of it as building a sequence:

n = 3, k = 2, target = 5
(3 dice, each with faces [1, 2])

First die rolls 1:
  Need remaining 2 dice to sum to 4
  β†’ count(2, 4)

First die rolls 2:
  Need remaining 2 dice to sum to 3
  β†’ count(2, 3)

For each choice, recurse deeper:

count(2, 4):
  Second die rolls 1 β†’ count(1, 3)
  Second die rolls 2 β†’ count(1, 2)

count(1, 3):
  Third die rolls 1 β†’ count(0, 2) = 0 βœ—
  Third die rolls 2 β†’ count(0, 1) = 0 βœ—

count(1, 2):
  Third die rolls 1 β†’ count(0, 1) = 0 βœ—
  Third die rolls 2 β†’ count(0, 0) = 1 βœ“

Build the tree, count all paths to success!

πŸ“ Implementation

class Solution {
    private static final int MOD = 1000000007;

    public int numRollsToTarget(int n, int k, int target) {
        return helper(n, k, target);
    }

    private int helper(int n, int k, int target) {
        // Base cases
        if (n == 0 && target == 0) return 1; // Success!
        if (n == 0 || target <= 0) return 0; // Failure

        int ways = 0;

        // Try each possible face value
        for (int face = 1; face <= k; face++) {
            ways = (ways + helper(n - 1, k, target - face)) % MOD;
        }

        return ways;
    }
}

πŸ” Detailed Dry Run: n = 2, k = 2, target = 3

k = 2 means each die has faces [1, 2]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RECURSIVE TREE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

                    helper(2, 2, 3)
                    /            \
              face=1            face=2
         helper(1,2,2)       helper(1,2,1)
         /         \          /         \
     face=1     face=2    face=1     face=2
  h(0,2,1)   h(0,2,0)  h(0,2,0)   h(0,2,-1)
     0          1 βœ“       1 βœ“         0

Trace each path:

Path 1: Roll 1, then roll 1
  helper(2, 2, 3)
    face = 1 β†’ helper(1, 2, 2)
      face = 1 β†’ helper(0, 2, 1)
        n=0, target=1 β†’ return 0 βœ—

Path 2: Roll 1, then roll 2
  helper(2, 2, 3)
    face = 1 β†’ helper(1, 2, 2)
      face = 2 β†’ helper(0, 2, 0)
        n=0, target=0 β†’ return 1 βœ“

Path 3: Roll 2, then roll 1
  helper(2, 2, 3)
    face = 2 β†’ helper(1, 2, 1)
      face = 1 β†’ helper(0, 2, 0)
        n=0, target=0 β†’ return 1 βœ“

Path 4: Roll 2, then roll 2
  helper(2, 2, 3)
    face = 2 β†’ helper(1, 2, 1)
      face = 2 β†’ helper(0, 2, -1)
        target < 0 β†’ return 0 βœ—

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 2 ways βœ“
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Valid sequences:
  [1, 2] β†’ sum = 3 βœ“
  [2, 1] β†’ sum = 3 βœ“

Why This Is Slow

Time Complexity: O(k^n)
  - At each level, we branch k ways (k faces)
  - Tree depth is n (number of dice)
  - Total nodes: k^n

For n = 30, k = 30:
  30^30 β‰ˆ 2 Γ— 10^44 operations
  Way too slow! ❌

Overlapping subproblems:
  helper(10, 6, 30) called from multiple paths
  Same state recomputed many times

Need memoization! β†’

πŸ“Š Complexity Analysis

Time Complexity: O(k^n) 

Exponential - tries all possible roll sequences
For each die: k choices
Total: k Γ— k Γ— ... Γ— k (n times) = k^n

Space Complexity: O(n) 

Recursion stack depth = number of dice

🟑 Approach 2: Memoization (Top-Down DP)

πŸ“ Function Definition

Function Signature: 

int numRollsToTarget(int n, int k, int target)

What it represents:

Variables we track: - memo[dice][sum] = Number of ways to reach sum using dice remaining - If computed, reuse it! - If not computed (-1), compute and cache it!

Purpose: - Same recursive logic as brute force - But CACHE results for (dice, sum) states - Each unique state solved only ONCE!

Key Understanding: 

Without memo:
  helper(10, 6, 30) called many times
  Each time: explore all k branches βœ—

With memo:
  helper(10, 6, 30) called first time β†’ compute, cache
  Called again β†’ return cached result immediately βœ“

This transforms O(k^n) β†’ O(n Γ— target Γ— k)!

πŸ’‘ Intuition

Think of it as a lookup table:

State: (dice=2, target=7)
Question: "How many ways to reach 7 with 2 dice?"

First time:
  Compute by trying all faces (1 to k)
  Sum the recursive results
  Result: 6
  Store in memo[2][7] = 6

Second time same state appears:
  Check memo[2][7]
  Found! Return 6 immediately
  No recomputation!

The memo saves exponential work!

πŸ“ Implementation

class Solution {
    private static final int MOD = 1000000007;
    private int[][] memo;

    public int numRollsToTarget(int n, int k, int target) {
        // memo[dice][sum] = ways to reach sum with dice remaining
        memo = new int[n + 1][target + 1];

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= target; j++) {
                memo[i][j] = -1; // -1 means not computed
            }
        }

        return helper(n, k, target);
    }

    private int helper(int n, int k, int target) {
        // Base cases
        if (n == 0 && target == 0) return 1;
        if (n == 0 || target <= 0) return 0;

        // Check memo
        if (memo[n][target] != -1) {
            return memo[n][target];
        }

        int ways = 0;

        // Try each possible face value
        for (int face = 1; face <= k; face++) {
            if (target - face >= 0) {
                ways = (ways + helper(n - 1, k, target - face)) % MOD;
            }
        }

        // Cache result
        memo[n][target] = ways;
        return ways;
    }
}

πŸ” Detailed Dry Run: n = 2, k = 6, target = 7

memo = int[3][8] (all -1 initially)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
COMPUTATION WITH MEMOIZATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Call: helper(2, 6, 7)
  memo[2][7] = -1 (not computed)

  Try face = 1:
    Call: helper(1, 6, 6)
      memo[1][6] = -1 (not computed)

      Try face = 1:
        Call: helper(0, 6, 5)
          n=0, target>0 β†’ return 0

      Try face = 2:
        Call: helper(0, 6, 4)
          n=0, target>0 β†’ return 0

      ...

      Try face = 6:
        Call: helper(0, 6, 0)
          n=0, target=0 β†’ return 1 βœ“

      ways = 0+0+0+0+0+1 = 1
      memo[1][6] = 1 βœ“
      return 1

  Try face = 2:
    Call: helper(1, 6, 5)
      memo[1][5] = -1 (not computed)

      Try faces 1-6:
        Only face=5 reaches helper(0, 6, 0) = 1

      ways = 1
      memo[1][5] = 1 βœ“
      return 1

  Try face = 3:
    Call: helper(1, 6, 4)
      memo[1][4] = -1
      Similar computation...
      memo[1][4] = 1 βœ“
      return 1

  Try face = 4:
    Call: helper(1, 6, 3)
      memo[1][3] = 1 βœ“
      return 1

  Try face = 5:
    Call: helper(1, 6, 2)
      memo[1][2] = 1 βœ“
      return 1

  Try face = 6:
    Call: helper(1, 6, 1)
      memo[1][1] = 1 βœ“
      return 1

  ways = 1+1+1+1+1+1 = 6
  memo[2][7] = 6 βœ“
  return 6

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL MEMO STATE (selected entries):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

memo[1][1] = 1
memo[1][2] = 1
memo[1][3] = 1
memo[1][4] = 1
memo[1][5] = 1
memo[1][6] = 1
memo[2][7] = 6

Each state computed ONCE and cached! βœ“

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 6 βœ“
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Why This Works

KEY INSIGHT:
  Same (dice, target) state appears many times in recursion tree
  With memo: compute once, reuse many times

Example:
  State (1, 6) appears when:
    - First die rolled 1, need (1, 6)
    - Different path may also lead to (1, 6)

  Brute force: recompute each time
  Memoization: compute once, cache, reuse

Transforms exponential β†’ polynomial!

πŸ“Š Complexity Analysis

Time Complexity: O(n Γ— target Γ— k) 

n = number of dice
target = target sum
k = faces per die

Unique states: n Γ— target
For each state: try k faces
Total: O(n Γ— target Γ— k)

For n=30, target=500, k=30:
  30 Γ— 500 Γ— 30 = 450,000 operations

Much better than k^n! βœ“

Space Complexity: O(n Γ— target) 

Memo array: O(n Γ— target)
Recursion stack: O(n)
Total: O(n Γ— target)

🟒 Approach 3: Bottom-Up DP (Iterative)

πŸ“ Function Definition

Function Signature: 

int numRollsToTarget(int n, int k, int target)

What it represents:

DP Array: - dp[dice][sum] = Number of ways to get sum using dice number of dice - Build from dp[0][...] up to dp[n][...] - Each cell computed from previous row

Purpose: - No recursion, build iteratively - For each die, try all faces - For each sum, accumulate ways from previous die

Key Understanding: 

State transition:

To reach sum S using D dice:
  Sum ways from previous (D-1) dice:
    - If previous sum was S-1, rolled face 1
    - If previous sum was S-2, rolled face 2
    - ...
    - If previous sum was S-k, rolled face k

dp[D][S] = Ξ£ dp[D-1][S-face] for face in [1..k]

Base case:
  dp[0][0] = 1 (0 dice, sum 0 β†’ 1 way)
  dp[0][anything else] = 0

Answer: dp[n][target]

πŸ’‘ Intuition

Think of building a table row by row:

Rows = number of dice used
Columns = possible sums

dp[0][0] = 1 (no dice, sum 0)

For 1 die (k=6):
  dp[1][1] = 1 (roll 1)
  dp[1][2] = 1 (roll 2)
  dp[1][3] = 1 (roll 3)
  dp[1][4] = 1 (roll 4)
  dp[1][5] = 1 (roll 5)
  dp[1][6] = 1 (roll 6)

For 2 dice:
  dp[2][2] = ways to get 2 with 2 dice
           = dp[1][1] (if second die rolls 1)
           = 1

  dp[2][7] = ways to get 7 with 2 dice
           = dp[1][6] (if second die rolls 1) +
             dp[1][5] (if second die rolls 2) +
             dp[1][4] (if second die rolls 3) +
             dp[1][3] (if second die rolls 4) +
             dp[1][2] (if second die rolls 5) +
             dp[1][1] (if second die rolls 6)
           = 1 + 1 + 1 + 1 + 1 + 1 = 6 βœ“

Build systematically!

πŸ“ Implementation

class Solution {
    private static final int MOD = 1000000007;

    public int numRollsToTarget(int n, int k, int target) {
        // dp[dice][sum] = ways to get sum using dice number of dice
        int[][] dp = new int[n + 1][target + 1];

        // Base case: 0 dice, sum 0
        dp[0][0] = 1;

        // Fill table
        for (int dice = 1; dice <= n; dice++) {
            for (int sum = 1; sum <= target; sum++) {
                // Try each face value
                for (int face = 1; face <= k; face++) {
                    if (sum - face >= 0) {
                        dp[dice][sum] = (dp[dice][sum] + dp[dice - 1][sum - face]) % MOD;
                    }
                }
            }
        }

        return dp[n][target];
    }
}

πŸ” Detailed Dry Run: n = 2, k = 2, target = 3

k = 2 means faces [1, 2]

Initial state:
dp = int[3][4]

dp[0][0] = 1 (base case)
All other entries = 0

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
BUILD DP TABLE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

After initialization:
      sum: 0  1  2  3
dice 0:    1  0  0  0
dice 1:    0  0  0  0
dice 2:    0  0  0  0

Process dice = 1:
━━━━━━━━━━━━━━━━━━━━

For sum = 1:
  face = 1: dp[1][1] += dp[0][0] = 0 + 1 = 1
  face = 2: dp[1][1] += dp[0][-1] β†’ skip (invalid)
  dp[1][1] = 1

For sum = 2:
  face = 1: dp[1][2] += dp[0][1] = 0 + 0 = 0
  face = 2: dp[1][2] += dp[0][0] = 0 + 1 = 1
  dp[1][2] = 1

For sum = 3:
  face = 1: dp[1][3] += dp[0][2] = 0 + 0 = 0
  face = 2: dp[1][3] += dp[0][1] = 0 + 0 = 0
  dp[1][3] = 0

After dice 1:
      sum: 0  1  2  3
dice 0:    1  0  0  0
dice 1:    0  1  1  0
dice 2:    0  0  0  0

Meaning: With 1 die, can get sum 1 or 2 (each 1 way)

Process dice = 2:
━━━━━━━━━━━━━━━━━━━━

For sum = 1:
  face = 1: dp[2][1] += dp[1][0] = 0 + 0 = 0
  face = 2: dp[2][1] += dp[1][-1] β†’ skip
  dp[2][1] = 0

For sum = 2:
  face = 1: dp[2][2] += dp[1][1] = 0 + 1 = 1
  face = 2: dp[2][2] += dp[1][0] = 1 + 0 = 1
  dp[2][2] = 1

For sum = 3:
  face = 1: dp[2][3] += dp[1][2] = 0 + 1 = 1
  face = 2: dp[2][3] += dp[1][1] = 1 + 1 = 2
  dp[2][3] = 2 βœ“

After dice 2:
      sum: 0  1  2  3
dice 0:    1  0  0  0
dice 1:    0  1  1  0
dice 2:    0  0  1  2

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: dp[2][3] = 2 βœ“
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Interpretation:
  With 2 dice (faces [1,2]), to get sum 3:
    - Roll [1, 2] β†’ sum = 3
    - Roll [2, 1] β†’ sum = 3
  Total: 2 ways βœ“

Understanding the Transition

Key insight for dp[2][3]:

To get sum 3 with 2 dice:

  If last die rolled 1:
    Previous dice must sum to 3-1=2
    Ways: dp[1][2] = 1
    (This is the sequence [2, 1])

  If last die rolled 2:
    Previous dice must sum to 3-2=1
    Ways: dp[1][1] = 1
    (This is the sequence [1, 2])

  Total: 1 + 1 = 2 βœ“

Each face contributes ways from previous row!

Space Optimization (Optional)

// Since we only need previous row, use 1D array
class Solution {
    private static final int MOD = 1000000007;

    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[] newDp = new int[target + 1];
            for (int sum = 1; sum <= target; sum++) {
                for (int face = 1; face <= k; face++) {
                    if (sum - face >= 0) {
                        newDp[sum] = (newDp[sum] + dp[sum - face]) % MOD;
                    }
                }
            }
            dp = newDp;
        }

        return dp[target];
    }
}

πŸ“Š Complexity Analysis

Time Complexity: O(n Γ— target Γ— k) 

Three nested loops:
  - Outer: n iterations (dice)
  - Middle: target iterations (sums)
  - Inner: k iterations (faces)

Total: O(n Γ— target Γ— k)

For n=30, target=500, k=30:
  30 Γ— 500 Γ— 30 = 450,000 operations
  Very efficient! βœ“

Space Complexity: O(n Γ— target) or O(target) 

2D DP: O(n Γ— target)
1D optimized: O(target)

Space optimization possible! βœ“

πŸ“Š Approach Comparison

β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”
β”‚   NUMBER OF DICE ROLLS - APPROACH COMPARISON                 β”‚
β”œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€
β”‚ Approach     β”‚ Time          β”‚ Space       β”‚ Clarityβ”‚Interviewβ”‚
β”œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€β”€β”€β”€
β”‚ Brute Force  β”‚ O(k^n)        β”‚ O(n)        β”‚ High   β”‚ Start  β”‚
β”‚ Memoization  β”‚ O(nΓ—targetΓ—k) β”‚ O(nΓ—target) β”‚ Good   β”‚ Good   β”‚
β”‚ Bottom-Up 2D β”‚ O(nΓ—targetΓ—k) β”‚ O(nΓ—target) β”‚ Best βœ“ β”‚ Best βœ“ β”‚
β”‚ Bottom-Up 1D β”‚ O(nΓ—targetΓ—k) β”‚ O(target)   β”‚ Good   β”‚ Optimalβ”‚
β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”˜

For interviews: Show brute force, optimize to DP!

πŸ’» Complete Working Code

class Solution {
  private static final int MOD = 1000000007;

  public int numRollsToTarget(int n, int k, int target) {
    return bottomUpDP(n, k, target);
  }

  // Approach 3: Bottom-Up 2D DP - O(nΓ—targetΓ—k) time, O(nΓ—target) space
  private int bottomUpDP(int n, int k, int target) {
    int[][] dp = new int[n + 1][target + 1];
    dp[0][0] = 1;

    for (int dice = 1; dice <= n; dice++) {
      for (int sum = 1; sum <= target; sum++) {
        for (int face = 1; face <= k; face++) {
          if (sum - face >= 0) {
            dp[dice][sum] = (dp[dice][sum] + dp[dice - 1][sum - face]) % MOD;
          }
        }
      }
    }

    return dp[n][target];
  }

  // Approach 3b: Bottom-Up 1D DP - O(nΓ—targetΓ—k) time, O(target) space
  private int bottomUpDP1D(int n, int k, int target) {
    int[] dp = new int[target + 1];
    dp[0] = 1;

    for (int dice = 1; dice <= n; dice++) {
      int[] newDp = new int[target + 1];
      for (int sum = 1; sum <= target; sum++) {
        for (int face = 1; face <= k; face++) {
          if (sum - face >= 0) {
            newDp[sum] = (newDp[sum] + dp[sum - face]) % MOD;
          }
        }
      }
      dp = newDp;
    }

    return dp[target];
  }

  // Approach 2: Memoization - O(nΓ—targetΓ—k) time, O(nΓ—target) space
  private int[][] memo;

  private int memoization(int n, int k, int target) {
    memo = new int[n + 1][target + 1];
    for (int i = 0; i <= n; i++) {
      for (int j = 0; j <= target; j++) {
        memo[i][j] = -1;
      }
    }
    return helperMemo(n, k, target);
  }

  private int helperMemo(int n, int k, int target) {
    if (n == 0 && target == 0)
      return 1;
    if (n == 0 || target <= 0)
      return 0;

    if (memo[n][target] != -1) {
      return memo[n][target];
    }

    int ways = 0;
    for (int face = 1; face <= k; face++) {
      if (target - face >= 0) {
        ways = (ways + helperMemo(n - 1, k, target - face)) % MOD;
      }
    }

    memo[n][target] = ways;
    return ways;
  }

  // Approach 1: Brute Force - O(k^n) time
  private int bruteForce(int n, int k, int target) {
    return helperBrute(n, k, target);
  }

  private int helperBrute(int n, int k, int target) {
    if (n == 0 && target == 0)
      return 1;
    if (n == 0 || target <= 0)
      return 0;

    int ways = 0;
    for (int face = 1; face <= k; face++) {
      ways = (ways + helperBrute(n - 1, k, target - face)) % MOD;
    }

    return ways;
  }

  public static void main(String[] args) {
    Solution s = new Solution();

    System.out.println(s.numRollsToTarget(1, 6, 3) == 1);
    System.out.println(s.numRollsToTarget(2, 6, 7) == 6);
    System.out.println(s.numRollsToTarget(30, 30, 500) == 222616187);
  }
}

πŸ”‘ Key Insights

The Recursive Structure

Critical Realization: 

To count ways with n dice to reach target:
  - For each face on current die (1 to k)
  - Recursively count ways with (n-1) dice to reach (target - face)
  - Sum all possibilities

count(n, target) = Ξ£ count(n-1, target-face) for face in [1..k]

This is natural recursion - each die is independent!

The State Definition

Understanding the 2D state: 

State: (dice_remaining, target_remaining)

Why 2D?
  - Need to track: how many dice left?
  - Need to track: what sum do we still need?

Both pieces of information are necessary!

This is different from Coin Change (1D state)
because dice count is bounded!

Pattern Recognition

How to spot this in future: 

πŸ” TRIGGERS:
  βœ“ "Count ways" (not minimize/maximize)
  βœ“ Multiple independent items (dice)
  βœ“ Each item has limited choices (faces)
  βœ“ Bounded count (exactly n dice)
  βœ“ Sum to reach target

🧠 THINK:
  "Is this counting combinations?"
  "Do I need bounded items?"
  "Is state 2D (count + sum)?"

πŸ’‘ RECOGNIZE:
  This is counting DP with bounded items
  Similar to: Coin Change 2 but with limits
  State: 2D (items, target)
  Transition: sum over all choices

Connection to Similar Problems

Coin Change 2 (Problem 231):
  β†’ Count ways, UNLIMITED coins
  β†’ 1D state (just target)
  β†’ Unbounded items

This Problem:
  β†’ Count ways, EXACTLY n dice
  β†’ 2D state (dice + target)
  β†’ Bounded items

Partition Equal Subset Sum (Problem 228):
  β†’ True/false, exactly once per item
  β†’ 1D state (target)
  β†’ 0/1 choice per item

All use DP, but different structures! 🎯

πŸŽͺ Memory Aid

"For each die, try all faces!"
"Sum ways from previous dice!"
"State = (dice_left, target_left)!"
"Counting DP with bounded items!" ✨

⚠️ Common Mistakes

  • ❌ Forgetting base case: n=0, target=0 β†’ return 1
  • ❌ Not checking target <= 0 β†’ return 0
  • ❌ Using 1D DP (need 2D for dice count!)
  • ❌ Forgetting modulo 10^9+7
  • ❌ Not handling edge case: target > n*k (impossible)

βœ… Interview Talking Points

"This is a counting problem with bounded items.

Discovery through examples:
  With 2 dice and target 7, I see there are 6 ways.
  For each value on first die (1-6), I need remaining
  dice to sum to (7 - first_die_value).

  This creates natural recursion!

Recursive structure:
  count(n dice, target) = Ξ£ count(n-1, target-face)
  for all face values from 1 to k

  Base cases:
    - n=0, target=0 β†’ 1 (success!)
    - n=0, target>0 β†’ 0 (failed)

State definition:
  Need 2D: (dice_remaining, target_remaining)
  Can't use 1D because dice count matters!

DP Solution:
  dp[dice][sum] = ways to get sum using dice number of dice

  For each dice from 1 to n:
    For each sum from 1 to target:
      For each face from 1 to k:
        dp[dice][sum] += dp[dice-1][sum-face]

  Answer: dp[n][target]

Optimization:
  Can reduce to 1D by keeping only previous row
  Space: O(nΓ—target) β†’ O(target)

Complexity: O(n Γ— target Γ— k) time
  Much better than O(k^n) brute force!

This is similar to Coin Change 2, but with bounded items
instead of unlimited coins!"

πŸ“ Quick Revision Notes

🎯 Core Concept

Problem Type: Count ways to reach target sum using exactly n dice (each with k faces)

Key Discovery: For each die, try all face values (1 to k), recursively count ways with remaining dice

Recursive Formula: count(n, target) = Ξ£ count(n-1, target-face) for face in [1..k]

⚑ Quick Implementation

// Bottom-Up 2D DP
public class Solution {
  public int numRollsToTarget(int n, int k, int target) {
    // return recursive(n, k, target);

    // Integer[][] memo = new Integer[n + 1][target + 1];
    // return topDown(n, k, target, memo);

    return bottomUp(n, k, target);
  }

  private int bottomUp(int n, int k, int target) {
    int MOD = 1000000007;
    int[][] dp = new int[n + 1][target + 1];

    // base case
    dp[0][0] = 1;

    // dp[0][1...target]?
    // can we achieve any target > 0 with 0 dice left? NO. Hence, default 0.

    // dp[1...n][0]?
    // can we achieve 0 target with any dice have faces 1...k? NO

    // building solution for [1...n] dice with [1...target] with [1...k] faces
    // dp[i][j] => number of ways to achieve target j with i number of dice.
    // finally we need dp[n][target]. We are building from bottom to end.
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= target; j++) {
        int ways = 0;
        for (int face = 1; face <= k; face++) {
          if (j - face >= 0) {
            ways = (ways + dp[i - 1][j - face]) % MOD;
          }
        }

        dp[i][j] = ways;
      }
    }

    return dp[n][target];
  }

  private int topDown(int n, int k, int target, Integer[][] memo) {
    int MOD = 1000000007;

    if (target == 0 && n == 0) {
      return 1;
    }

    if (n < 0 || target <= 0) {
      return 0;
    }

    if (memo[n][target] != null) {
      return memo[n][target];
    }

    int ways = 0;
    for (int i = 1; i <= k; i++) {
      ways = (ways + topDown(n - 1, k, target - i, memo)) % MOD;
    }

    return memo[n][target] = ways;
  }

  private int recursive(int n, int k, int target) {
    int MOD = 1000000007;

    // step 3: base case 1
    if (target == 0 && n == 0) {
      return 1;
    }

    // step 4: base case 2
    if (n < 0 || target <= 0) {
      return 0;
    }

    // step 1: out of n dice, using only 1 with k faces.
    int ways = 0;
    for (int i = 1; i <= k; i++) {
      // step 2:
      // when 1 dice used, use remaining n-1 dice to achieve remaining target
      ways = (ways + recursive(n - 1, k, target - i)) % MOD;
    }

    return ways;
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.numRollsToTarget(1, 6, 3) == 1);
    System.out.println(s.numRollsToTarget(2, 6, 7) == 6);
    System.out.println(s.numRollsToTarget(30, 30, 500) == 222616187);
  }
}

Complexity: O(n Γ— target Γ— k) time, O(n Γ— target) space

πŸ”‘ Key Points

The State: 

2D State: (dice_remaining, target_remaining)

Why 2D?
  - Dice count is bounded (exactly n)
  - Need to track both dice left AND sum needed

This differs from Coin Change (unbounded β†’ 1D)

The Transition: 

To get sum S with D dice:
  Try all faces (1 to k):
    If face F: need (S-F) from (D-1) dice
    Sum all these ways!

dp[D][S] = Ξ£ dp[D-1][S-face] for all faces

Base Cases: 

dp[0][0] = 1 (0 dice, sum 0 β†’ success!)
All other dp[0][x] = 0 (can't make non-zero sum with 0 dice)

πŸ’‘ Recognition

See "count ways" + "exactly n items" + "sum to target" β†’ Think bounded counting DP! - Similar to Coin Change 2 (unbounded) - But need 2D state (bounded by n) - Sum over all choices per item

⚠️ Common Traps

  • ❌ Using 1D DP (need 2D for dice count!)
  • ❌ Forgetting modulo operations
  • ❌ Wrong base case (dp[0][0] = 1, not 0!)
  • ❌ Not checking sum-face >= 0

πŸŽ‰ Congratulations!

You've learned to: - βœ… Discover the pattern through small examples - βœ… Recognize recursive structure naturally - βœ… Define 2D state for bounded items - βœ… Implement all three approaches - βœ… Optimize space with 1D array - βœ… Connect to similar counting problems

This is counting DP with bounded items - a fundamental pattern! πŸš€βœ¨