Problem

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 kn 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.

Examples

Example 1:

1
2
3
4
5
6

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:

1
2
3
4
5
6

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:

1
2
3
4
5

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

Solution

Method 1 – DP with Memoization

Intuition

We use recursion with memoization to count the number of ways to roll n dice with k faces to reach the target sum. For each die, we try all possible face values and recursively solve for the remaining dice and target.

Approach

  1. Define a recursive function with parameters: number of dice left and remaining target sum.
  2. If target < 0, return 0 (invalid sum).
  3. If no dice left, return 1 if target == 0, else 0.
  4. For each face value from 1 to k, subtract it from target and recurse for the next die.
  5. Use memoization to cache results for each (dice, target) pair.

Recurrence Relation:

Let f(n, target) be the number of ways to roll n dice to sum to target.

1

f(n, target) = sum_{i=1}^{k} f(n-1, target-i)

Base Case:

  • If target < 0: return 0
  • If n == 0: return 1 if target == 0 else 0

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
	int numRollsToTarget(int n, int k, int target) {
		const int MOD = 1e9 + 7;
		vector<vector<int>> dp(n + 1, vector<int>(target + 1, -1));
		return helper(n, k, target, dp, MOD);
	}
private:
	int helper(int n, int k, int target, vector<vector<int>>& dp, int MOD) {
		if (target < 0) return 0;
		if (n == 0) return target == 0 ? 1 : 0;
		if (dp[n][target] != -1) return dp[n][target];
		int ans = 0;
		for (int i = 1; i <= k; ++i) {
			ans = (ans + helper(n - 1, k, target - i, dp, MOD)) % MOD;
		}
		return dp[n][target] = ans;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

func numRollsToTarget(n int, k int, target int) int {
	const MOD int = 1e9 + 7
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, target+1)
		for j := range dp[i] {
			dp[i][j] = -1
		}
	}
	var helper func(n, t int) int
	helper = func(n, t int) int {
		if t < 0 {
			return 0
		}
		if n == 0 {
			if t == 0 {
				return 1
			}
			return 0
		}
		if dp[n][t] != -1 {
			return dp[n][t]
		}
		ans := 0
		for i := 1; i <= k; i++ {
			ans = (ans + helper(n-1, t-i)) % MOD
		}
		dp[n][t] = ans
		return ans
	}
	return helper(n, target)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
	private static final int MOD = 1000000007;
	public int numRollsToTarget(int n, int k, int target) {
		Integer[][] dp = new Integer[n + 1][target + 1];
		return helper(n, k, target, dp);
	}
	private int helper(int n, int k, int target, Integer[][] dp) {
		if (target < 0) return 0;
		if (n == 0) return target == 0 ? 1 : 0;
		if (dp[n][target] != null) return dp[n][target];
		int ans = 0;
		for (int i = 1; i <= k; i++) {
			ans = (ans + helper(n - 1, k, target - i, dp)) % MOD;
		}
		return dp[n][target] = ans;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
	private val MOD = 1000000007
	fun numRollsToTarget(n: Int, k: Int, target: Int): Int {
		val dp = Array(n + 1) { Array(target + 1) { -1 } }
		fun helper(n: Int, t: Int): Int {
			if (t < 0) return 0
			if (n == 0) return if (t == 0) 1 else 0
			if (dp[n][t] != -1) return dp[n][t]
			var ans = 0
			for (i in 1..k) {
				ans = (ans + helper(n - 1, t - i)) % MOD
			}
			dp[n][t] = ans
			return ans
		}
		return helper(n, target)
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
	def numRollsToTarget(self, n: int, k: int, target: int) -> int:
		MOD = 10**9 + 7
		dp = [[-1] * (target + 1) for _ in range(n + 1)]
		def helper(n: int, t: int) -> int:
			if t < 0:
				return 0
			if n == 0:
				return 1 if t == 0 else 0
			if dp[n][t] != -1:
				return dp[n][t]
			ans = 0
			for i in range(1, k + 1):
				ans = (ans + helper(n - 1, t - i)) % MOD
			dp[n][t] = ans
			return ans
		return helper(n, target)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

impl Solution {
	pub fn num_rolls_to_target(n: i32, k: i32, target: i32) -> i32 {
		const MOD: i32 = 1_000_000_007;
		let n = n as usize;
		let target = target as usize;
		let k = k as usize;
		let mut dp = vec![vec![-1; target + 1]; n + 1];
		fn helper(n: usize, k: usize, t: usize, dp: &mut Vec<Vec<i32>>) -> i32 {
			if t < 0 { return 0; }
			if n == 0 { return if t == 0 { 1 } else { 0 }; }
			if dp[n][t] != -1 { return dp[n][t]; }
			let mut ans = 0;
			for i in 1..=k {
				if t >= i {
					ans = (ans + helper(n - 1, k, t - i, dp)) % MOD;
				}
			}
			dp[n][t] = ans;
			ans
		}
		helper(n, k, target, &mut dp)
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
	numRollsToTarget(n: number, k: number, target: number): number {
		const MOD = 1e9 + 7;
		const dp: number[][] = Array.from({ length: n + 1 }, () => Array(target + 1).fill(-1));
		function helper(n: number, t: number): number {
			if (t < 0) return 0;
			if (n === 0) return t === 0 ? 1 : 0;
			if (dp[n][t] !== -1) return dp[n][t];
			let ans = 0;
			for (let i = 1; i <= k; i++) {
				ans = (ans + helper(n - 1, t - i)) % MOD;
			}
			dp[n][t] = ans;
			return ans;
		}
		return helper(n, target);
	}
}

Complexity

  • ⏰ Time complexity: O(n * k * target) — For each dice and target, we try all k faces.
  • 🧺 Space complexity: O(n * target) — DP table stores results for each dice and target sum.

Method 2 – Bottom Up DP

Intuition

We use dynamic programming to iteratively build the number of ways to reach each sum with a given number of dice. For each dice and each possible sum, we add up the ways to reach that sum by considering all possible face values.

Approach

  1. Create a DP table dp[i][j] where i is the number of dice and j is the target sum.
  2. Initialize dp[0][0] = 1 (one way to reach sum 0 with 0 dice).
  3. For each dice from 1 to n, for each sum from 1 to target, for each face value from 1 to k, add the ways from previous dice and sum.
  4. Use modulo 10^9 + 7 to keep the result within bounds.

Recurrence Relation:

Let dp[i][j] be the number of ways to get sum j with i dice.

1

dp[i][j] = sum_{face=1}^{k} dp[i-1][j-face]

Base Case:

  • dp[0][0] = 1 (one way to reach sum 0 with 0 dice)
  • dp[0][j] = 0 for j > 0

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
	int numRollsToTarget(int n, int k, int target) {
		const int MOD = 1e9 + 7;
		vector<vector<int>> dp(n + 1, vector<int>(target + 1, 0));
		dp[0][0] = 1;
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= target; ++j) {
				for (int face = 1; face <= k && face <= j; ++face) {
					dp[i][j] = (dp[i][j] + dp[i-1][j-face]) % MOD;
				}
			}
		}
		return dp[n][target];
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func numRollsToTarget(n int, k int, target int) int {
	const MOD int = 1e9 + 7
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, target+1)
	}
	dp[0][0] = 1
	for i := 1; i <= n; i++ {
		for j := 1; j <= target; j++ {
			for face := 1; face <= k && face <= j; face++ {
				dp[i][j] = (dp[i][j] + dp[i-1][j-face]) % MOD
			}
		}
	}
	return dp[n][target]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
	private static final int MOD = 1000000007;
	public int numRollsToTarget(int n, int k, int target) {
		int[][] dp = new int[n + 1][target + 1];
		dp[0][0] = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= target; j++) {
				for (int face = 1; face <= k && face <= j; face++) {
					dp[i][j] = (dp[i][j] + dp[i-1][j-face]) % MOD;
				}
			}
		}
		return dp[n][target];
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
	private val MOD = 1000000007
	fun numRollsToTarget(n: Int, k: Int, target: Int): Int {
		val dp = Array(n + 1) { IntArray(target + 1) }
		dp[0][0] = 1
		for (i in 1..n) {
			for (j in 1..target) {
				for (face in 1..minOf(k, j)) {
					dp[i][j] = (dp[i][j] + dp[i-1][j-face]) % MOD
				}
			}
		}
		return dp[n][target]
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
	def numRollsToTarget(self, n: int, k: int, target: int) -> int:
		MOD = 10**9 + 7
		dp = [[0] * (target + 1) for _ in range(n + 1)]
		dp[0][0] = 1
		for i in range(1, n + 1):
			for j in range(1, target + 1):
				for face in range(1, min(k, j) + 1):
					dp[i][j] = (dp[i][j] + dp[i-1][j-face]) % MOD
		return dp[n][target]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
	pub fn num_rolls_to_target(n: i32, k: i32, target: i32) -> i32 {
		const MOD: i32 = 1_000_000_007;
		let n = n as usize;
		let target = target as usize;
		let k = k as usize;
		let mut dp = vec![vec![0; target + 1]; n + 1];
		dp[0][0] = 1;
		for i in 1..=n {
			for j in 1..=target {
				for face in 1..=k.min(j) {
					dp[i][j] = (dp[i][j] + dp[i-1][j-face]) % MOD;
				}
			}
		}
		dp[n][target]
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
	numRollsToTarget(n: number, k: number, target: number): number {
		const MOD = 1e9 + 7;
		const dp: number[][] = Array.from({ length: n + 1 }, () => Array(target + 1).fill(0));
		dp[0][0] = 1;
		for (let i = 1; i <= n; i++) {
			for (let j = 1; j <= target; j++) {
				for (let face = 1; face <= k && face <= j; face++) {
					dp[i][j] = (dp[i][j] + dp[i-1][j-face]) % MOD;
				}
			}
		}
		return dp[n][target];
	}
}

Complexity

  • ⏰ Time complexity: O(n * k * target) — For each dice and target, we try all k faces.
  • 🧺 Space complexity: O(n * target) — DP table stores results for each dice and target sum.

Method 3 – Bottom Up DP (Time and Space Optimized)

Intuition

We further optimize space by using two 1D arrays and prefix sums, keeping only the current and previous states. This reduces space usage from O(n * target) to O(target).

Approach

  1. Use two arrays dp1 and dp2 of size target + 1 to store the number of ways for the previous and current dice.
  2. Initialize dp1[0] = 1 (one way to reach sum 0 with 0 dice).
  3. For each dice from 1 to n, use prefix sums to update dp2 for all possible sums.
  4. Swap arrays after each dice iteration.
  5. Use modulo 10^9 + 7 to keep the result within bounds.

Recurrence Relation:

Let dp[j] be the number of ways to get sum j with current dice.

1

dp2[j] = prefix_sum[j-1] - (j >= k ? prefix_sum[j-k-1] : 0)

Base Case:

  • dp1[0] = 1 (one way to reach sum 0 with 0 dice)
  • dp1[j] = 0 for j > 0

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
	int numRollsToTarget(int n, int k, int target) {
		const int MOD = 1e9 + 7;
		vector<int> dp1(target + 1, 0), dp2(target + 1, 0);
		dp1[0] = 1;
		for (int i = 1; i <= n; ++i) {
			int prefix = dp1[0];
			for (int j = 1; j <= target; ++j) {
				dp2[j] = prefix;
				prefix = (prefix + dp1[j]) % MOD;
				if (j >= k) {
					prefix = (prefix - dp1[j - k] + MOD) % MOD;
				}
			}
			dp1 = dp2;
			fill(dp2.begin(), dp2.end(), 0);
		}
		return dp1[target];
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func numRollsToTarget(n int, k int, target int) int {
	const MOD int = 1e9 + 7
	dp1 := make([]int, target+1)
	dp2 := make([]int, target+1)
	dp1[0] = 1
	for i := 1; i <= n; i++ {
		prefix := dp1[0]
		for j := 1; j <= target; j++ {
			dp2[j] = prefix
			prefix = (prefix + dp1[j]) % MOD
			if j >= k {
				prefix = (prefix - dp1[j-k] + MOD) % MOD
			}
		}
		copy(dp1, dp2)
		for j := range dp2 {
			dp2[j] = 0
		}
	}
	return dp1[target]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
	private static final int MOD = 1000000007;
	public int numRollsToTarget(int n, int k, int target) {
		int[] dp1 = new int[target + 1];
		int[] dp2 = new int[target + 1];
		dp1[0] = 1;
		for (int i = 1; i <= n; i++) {
			int prefix = dp1[0];
			for (int j = 1; j <= target; j++) {
				dp2[j] = prefix;
				prefix = (prefix + dp1[j]) % MOD;
				if (j >= k) {
					prefix = (prefix - dp1[j - k] + MOD) % MOD;
				}
			}
			int[] temp = dp1;
			dp1 = dp2;
			dp2 = temp;
			dp2[0] = 0;
		}
		return dp1[target];
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
	private val MOD = 1000000007
	fun numRollsToTarget(n: Int, k: Int, target: Int): Int {
		var dp1 = IntArray(target + 1)
		var dp2 = IntArray(target + 1)
		dp1[0] = 1
		for (i in 1..n) {
			var prefix = dp1[0]
			for (j in 1..target) {
				dp2[j] = prefix
				prefix = (prefix + dp1[j]) % MOD
				if (j >= k) {
					prefix = (prefix - dp1[j - k] + MOD) % MOD
				}
			}
			dp1 = dp2.also { dp2 = dp1 }
			dp2[0] = 0
		}
		return dp1[target]
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
	def numRollsToTarget(self, n: int, k: int, target: int) -> int:
		MOD = 10**9 + 7
		dp1 = [0] * (target + 1)
		dp2 = [0] * (target + 1)
		dp1[0] = 1
		for _ in range(1, n + 1):
			prefix = dp1[0]
			for j in range(1, target + 1):
				dp2[j] = prefix
				prefix = (prefix + dp1[j]) % MOD
				if j >= k:
					prefix = (prefix - dp1[j - k] + MOD) % MOD
			dp1, dp2 = dp2, dp1
			dp2[0] = 0
		return dp1[target]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

impl Solution {
	pub fn num_rolls_to_target(n: i32, k: i32, target: i32) -> i32 {
		const MOD: i32 = 1_000_000_007;
		let n = n as usize;
		let target = target as usize;
		let k = k as usize;
		let mut dp1 = vec![0; target + 1];
		let mut dp2 = vec![0; target + 1];
		dp1[0] = 1;
		for _ in 1..=n {
			let mut prefix = dp1[0];
			for j in 1..=target {
				dp2[j] = prefix;
				prefix = (prefix + dp1[j]) % MOD;
				if j >= k {
					prefix = (prefix - dp1[j - k] + MOD) % MOD;
				}
			}
			dp1.copy_from_slice(&dp2);
			dp2.fill(0);
		}
		dp1[target]
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
	numRollsToTarget(n: number, k: number, target: number): number {
		const MOD = 1e9 + 7;
		let dp1 = new Array(target + 1).fill(0);
		let dp2 = new Array(target + 1).fill(0);
		dp1[0] = 1;
		for (let i = 1; i <= n; i++) {
			let prefix = dp1[0];
			for (let j = 1; j <= target; j++) {
				dp2[j] = prefix;
				prefix = (prefix + dp1[j]) % MOD;
				if (j >= k) {
					prefix = (prefix - dp1[j - k] + MOD) % MOD;
				}
			}
			[dp1, dp2] = [dp2, dp1];
			dp2[0] = 0;
		}
		return dp1[target];
	}
}

Complexity

  • ⏰ Time complexity: O(n * target) — For each dice and target, we use prefix sums to optimize the calculation.
  • 🧺 Space complexity: O(target) — Only two arrays of size target are used for DP.