Number of Dice Rolls With Target Sum solution and explanation
Google
9 more videos on this problem
Number of Dice Rolls with Target Sum - Leetcode 1155 - PythonNeetCodeIO · 20:20 · 23K views
Number of Dice Rolls With Target Sum | Recursion | Memo | Bottom Up | Leetcode 1155codestorywithMIK · 28:40 · 7K views
LeetCode 1155. Number of Dice Rolls With Target Sum Explanation and Solutionhappygirlzt · 8:21 · 4K views
Leetcode 1155 Number of Dice Rolls With Target Sum | Coding Decoded SDE SheetCoding Decoded · 6:30 · 3K views
1155. Number of Dice Rolls With Target Sum | 2D DPAryan Mittal · 17:30 · 3K views
Daily Leetcode #915: Oct 02, 2022 - 1155. Number of Dice Rolls With Target SumProgramming Live with Larry · 8:34 · 1K views
LeetCode 1155 Number of Dice Rolls With Target SumcoderZ · 7:34 · 1K views
Leetcode 1155 | Number of Dice Rolls With Target Sum | Java | Dynamic ProgrammingPessimist Programmer · 10:34 · 1K views
1155. Number of Dice Rolls With Target Sum || Python || LeetCodeThe Local Coder! · 9:29 · 698 views
Number of Dice Rolls With Target Sum | LeetCode 1155 | Amazon Interview Question @LearnOverflowLearn Overflow · 19:30 · 491 views
The problem
You have n dice, and each dice 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 109 + 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 109 + 7.
Constraints:
1 <= n, k <= 301 <= target <= 1000
Approach overview
Problem Overview: You roll n dice, each with k faces numbered from 1 to k. Count how many possible combinations produce an exact sum equal to target. The result must be returned modulo 1e9 + 7. The challenge is efficiently counting combinations without enumerating every possible roll.
Approach 1: Recursive with Memoization (Time: O(n * k * target), Space: O(n * target))
This approach models the problem as a recursive decision tree. For each die, you try every face value from 1 to k and reduce the remaining target accordingly. The state can be defined as (dice_remaining, remaining_sum). Without caching, many states repeat, causing exponential time. Memoization stores results for each state in a lookup table so repeated calls return instantly. This converts the recursion into a top‑down dynamic programming solution. The recursion depth equals the number of dice, and memoization ensures each state is computed only once.
Approach 2: Bottom-Up Dynamic Programming (Time: O(n * k * target), Space: O(n * target))
The bottom-up DP version builds the solution iteratively. Define dp[i][s] as the number of ways to get sum s using i dice. Start with the base case dp[0][0] = 1. For each dice count from 1 to n, iterate through all possible sums and accumulate contributions from the previous row: dp[i][s] += dp[i-1][s-face] for every face value 1..k. This approach avoids recursion and is often easier to reason about in interviews. The transition mirrors the recurrence used in the recursive solution but computed iteratively using a DP table.
Recommended for interviews: Start by describing the recursive state definition and recurrence to demonstrate understanding of the combinatorial structure. Then move to memoization or bottom-up dynamic programming to eliminate repeated work. Interviewers typically expect the DP formulation with complexity O(n * k * target), since brute force enumeration would be exponential and impractical.
Approach 1: Approach 1: Recursive with Memoization
We utilize recursion to explore different combinations of dice rolls to reach the target sum. For every die, we try all face values and keep track of the sum formed. To avoid redundant calculations, we use memoization.
MOD = 10**9 + 7
def numRollsToTarget(n, k, target):
memo = [[-1] * (target + 1) for _ in range(n + 1)]
def dfs(dice, target):
if dice == 0:
return 1 if target == 0 else 0
if target < 0:
return 0
if memo[dice][target] != -1:
return memo[dice][target]
count = 0
for i in range(1, k + 1):
count = (count + dfs(dice - 1, target - i)) % MOD
memo[dice][target] = count
return count
return dfs(n, target)
print(numRollsToTarget(2, 6, 7)) # Output: 6import java.util.Arrays;
class Solution {
private static final int MOD = 1000000007;
public int numRollsToTarget(int n, int k, int target) {
int[][] memo = new int[n + 1][target + 1];
for (int[] m : memo) Arrays.fill(m, -1);
return dfs(n, target, k, memo);
}
private int dfs(int dice, int target, int k, int[][] memo) {
if (dice == 0) return target == 0 ? 1 : 0;
if (target <= 0) return 0;
if (memo[dice][target] != -1) return memo[dice][target];
int count = 0;
for (int i = 1; i <= k; i++) {
count = (count + dfs(dice - 1, target - i, k, memo)) % MOD;
}
return memo[dice][target] = count;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.numRollsToTarget(2, 6, 7)); // Output: 6
}
}#include <iostream>
#include <vector>
class Solution {
public:
int numRollsToTarget(int n, int k, int target) {
std::vector<std::vector<int>> memo(n + 1, std::vector<int>(target + 1, -1));
const int MOD = 1e9 + 7;
return dfs(n, target, k, memo, MOD);
}
private:
int dfs(int dice, int target, int k, std::vector<std::vector<int>>& memo, const int MOD) {
if (dice == 0) return target == 0 ? 1 : 0;
if (target <= 0) return 0;
if (memo[dice][target] != -1) return memo[dice][target];
int count = 0;
for (int i = 1; i <= k; ++i) {
count = (count + dfs(dice - 1, target - i, k, memo, MOD)) % MOD;
}
return memo[dice][target] = count;
}
};
int main() {
Solution sol;
std::cout << sol.numRollsToTarget(2, 6, 7) << std::endl; // Output: 6
return 0;
}const MOD = 1000000007;
function numRollsToTarget(n, k, target) {
const memo = Array.from({ length: n + 1 }, () => Array(target + 1).fill(-1));
function dfs(dice, target) {
if (dice === 0) return target === 0 ? 1 : 0;
if (target <= 0) return 0;
if (memo[dice][target] !== -1) return memo[dice][target];
let count = 0;
for (let i = 1; i <= k; i++) {
count = (count + dfs(dice - 1, target - i)) % MOD;
}
memo[dice][target] = count;
return count;
}
return dfs(n, target);
}
console.log(numRollsToTarget(2, 6, 7)); // Output: 6#include <stdio.h>
#include <string.h>
#define MOD 1000000007
int memo[31][1001];
int dfs(int dice, int target, int k) {
if (dice == 0) return target == 0;
if (target <= 0) return 0;
if (memo[dice][target] != -1) return memo[dice][target];
int count = 0;
for (int i = 1; i <= k; ++i) {
count = (count + dfs(dice - 1, target - i, k)) % MOD;
}
return memo[dice][target] = count;
}
int numRollsToTarget(int n, int k, int target) {
memset(memo, -1, sizeof(memo));
return dfs(n, target, k);
}
int main() {
printf("%d\n", numRollsToTarget(2, 6, 7)); // Output: 6
return 0;
}using System;
public class Solution {
private static readonly int MOD = 1000000007;
public int NumRollsToTarget(int n, int k, int target) {
var 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 Dfs(n, target, k, memo);
}
private int Dfs(int dice, int target, int k, int[,] memo) {
if (dice == 0) return target == 0 ? 1 : 0;
if (target <= 0) return 0;
if (memo[dice, target] != -1) return memo[dice, target];
int count = 0;
for (int i = 1; i <= k; ++i) {
count = (count + Dfs(dice - 1, target - i, k, memo)) % MOD;
}
return memo[dice, target] = count;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.NumRollsToTarget(2, 6, 7)); // Output: 6
}
}We define a recursive function dfs to attempt different face values for each die, decrementing dice and target step-wise. The results for already computed states are kept in a list named memo to prevent recomputation.
Time Complexity: O(n * target * k) represents recursive state explorations.
Space Complexity: O(n * target) given the size of memoization used.
Approach 2: Approach 2: Dynamic Programming
Use a Dynamic Programming (DP) table where dp[i][j] represents the number of ways to achieve sum j with i dice. Initially, only dp[0][0] = 1 since there's one way to roll zero dice to get zero sum. The state transition iterates over each dice and accumulates ways using previous results.
MOD = 10**9 + 7
def numRollsToTarget(n, k, target):
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 x in range(1, k + 1):
if j >= x:
dp[i][j] = (dp[i][j] + dp[i - 1][j - x]) % MOD
return dp[n][target]
print(numRollsToTarget(2, 6, 7)) # Output: 6class 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 x = 1; x <= k; x++) {
if (j >= x) {
dp[i][j] = (dp[i][j] + dp[i - 1][j - x]) % MOD;
}
}
}
}
return dp[n][target];
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.numRollsToTarget(2, 6, 7)); // Output: 6
}
}#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int numRollsToTarget(int n, int k, int target) {
vector<vector<int>> dp(n + 1, vector<int>(target + 1, 0));
const int MOD = 1e9 + 7;
dp[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= target; ++j) {
for (int x = 1; x <= k; ++x) {
if (j - x >= 0) {
dp[i][j] = (dp[i][j] + dp[i - 1][j - x]) % MOD;
}
}
}
}
return dp[n][target];
}
};
int main() {
Solution sol;
cout << sol.numRollsToTarget(2, 6, 7) << endl;
return 0;
}const MOD = 1000000007;
function numRollsToTarget(n, k, target) {
const dp = 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 x = 1; x <= k; x++) {
if (j >= x) {
dp[i][j] = (dp[i][j] + dp[i - 1][j - x]) % MOD;
}
}
}
}
return dp[n][target];
}
console.log(numRollsToTarget(2, 6, 7)); // Output: 6#include <stdio.h>
#include <string.h>
#define MOD 1000000007
int numRollsToTarget(int n, int k, int target) {
int dp[n + 1][target + 1];
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= target; ++j) {
for (int x = 1; x <= k; ++x) {
if (j - x >= 0) {
dp[i][j] = (dp[i][j] + dp[i - 1][j - x]) % MOD;
}
}
}
}
return dp[n][target];
}
int main() {
printf("%d\n", numRollsToTarget(2, 6, 7));
return 0;
}using System;
public class Solution {
public int NumRollsToTarget(int n, int k, int target) {
const int MOD = 1000000007;
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 x = 1; x <= k; x++) {
if (j >= x) {
dp[i, j] = (dp[i, j] + dp[i - 1, j - x]) % MOD;
}
}
}
}
return dp[n, target];
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.NumRollsToTarget(2, 6, 7)); // Output: 6
}
}The solution applies DP logic to process results by iterating constraints of dice and result values using accumulated states from previously computed possibilities.
Time Complexity: O(n * target * k) for complete evaluations of rolls and outcomes.
Space Complexity: O(n * target) via state information tables.
Approach 3: Dynamic Programming
We define f[i][j] as the number of ways to get a sum of j using i dice. Then, we can obtain the following state transition equation:
$
f[i][j] = sum_{h=1}^{min(j, k)} f[i-1][j-h]
where h represents the number of points on the i-th die.
Initially, we have f[0][0] = 1, and the final answer is f[n][target].
The time complexity is O(n times k times target), and the space complexity is O(n times target).
We notice that the state f[i][j] only depends on f[i-1][], so we can use a rolling array to optimize the space complexity to O(target)$.
function numRollsToTarget(n: number, k: number, target: number): number {
const f = Array.from({ length: n + 1 }, () => Array(target + 1).fill(0));
f[0][0] = 1;
const mod = 1e9 + 7;
for (let i = 1; i <= n; ++i) {
for (let j = 1; j <= Math.min(i * k, target); ++j) {
for (let h = 1; h <= Math.min(j, k); ++h) {
f[i][j] = (f[i][j] + f[i - 1][j - h]) % mod;
}
}
}
return f[n][target];
}func numRollsToTarget(n int, k int, target int) int {
const mod int = 1e9 + 7
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, target+1)
}
f[0][0] = 1
for i := 1; i <= n; i++ {
for j := 1; j <= min(target, i*k); j++ {
for h := 1; h <= min(j, k); h++ {
f[i][j] = (f[i][j] + f[i-1][j-h]) % mod
}
}
}
return f[n][target]
}impl Solution {
pub fn num_rolls_to_target(n: i32, k: i32, target: i32) -> i32 {
let _mod = 1_000_000_007;
let n = n as usize;
let k = k as usize;
let target = target as usize;
let mut f = vec![vec![0; target + 1]; n + 1];
f[0][0] = 1;
for i in 1..=n {
for j in 1..=target.min(i * k) {
for h in 1..=j.min(k) {
f[i][j] = (f[i][j] + f[i - 1][j - h]) % _mod;
}
}
}
f[n][target]
}
}Approach 4: Default Approach
function numRollsToTarget(n: number, k: number, target: number): number {
const f = Array(target + 1).fill(0);
f[0] = 1;
const mod = 1e9 + 7;
for (let i = 1; i <= n; ++i) {
const g = Array(target + 1).fill(0);
for (let j = 1; j <= Math.min(i * k, target); ++j) {
for (let h = 1; h <= Math.min(j, k); ++h) {
g[j] = (g[j] + f[j - h]) % mod;
}
}
f.splice(0, target + 1, ...g);
}
return f[target];
}func numRollsToTarget(n int, k int, target int) int {
const mod int = 1e9 + 7
f := make([]int, target+1)
f[0] = 1
for i := 1; i <= n; i++ {
g := make([]int, target+1)
for j := 1; j <= min(target, i*k); j++ {
for h := 1; h <= min(j, k); h++ {
g[j] = (g[j] + f[j-h]) % mod
}
}
f = g
}
return f[target]
}impl Solution {
pub fn num_rolls_to_target(n: i32, k: i32, target: i32) -> i32 {
let _mod = 1_000_000_007;
let n = n as usize;
let k = k as usize;
let target = target as usize;
let mut f = vec![0; target + 1];
f[0] = 1;
for i in 1..=n {
let mut g = vec![0; target + 1];
for j in 1..=target {
for h in 1..=j.min(k) {
g[j] = (g[j] + f[j - h]) % _mod;
}
}
f = g;
}
f[target]
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Recursive with Memoization | Time Complexity: O(n * target * k) represents recursive state explorations. |
| Approach 2: Dynamic Programming | Time Complexity: O(n * target * k) for complete evaluations of rolls and outcomes. |
| Dynamic Programming | – |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(n * k * target) | O(n * target) | When you want a natural recursive formulation and easy state definition |
| Bottom-Up Dynamic Programming | O(n * k * target) | O(n * target) | Preferred iterative solution for interviews and production code |
| Space-Optimized DP | O(n * k * target) | O(target) | When memory usage matters and only the previous dice state is needed |
Frequently asked questions
Is Number of Dice Rolls With Target Sum easy or hard?
LeetCode classifies this problem as Medium difficulty. The recurrence relation is straightforward, but recognizing the dynamic programming state and handling modulo arithmetic makes it slightly more challenging for beginners.
Number of Dice Rolls With Target Sum Python/Java solution
Both Python and Java implementations typically use dynamic programming. Python solutions often use recursion with functools.lru_cache or a DP list, while Java commonly uses a 2D int array dp[n+1][target+1] with modulo arithmetic for large counts.
How to solve Number of Dice Rolls With Target Sum in O(n)?
The problem cannot be solved in strict O(n) time because each dice roll introduces k possible face values and multiple target sums must be evaluated. The best known solution uses dynamic programming with O(n * k * target) complexity by computing combinations incrementally.
What is the best approach for Number of Dice Rolls With Target Sum?
Dynamic Programming is the most efficient approach. Define dp[i][s] as the number of ways to reach sum s using i dice. For each state, iterate over all k faces and accumulate transitions from dp[i-1][s-face]. This reduces the exponential brute force search to O(n * k * target) time.
Is Number of Dice Rolls With Target Sum asked at Google/Amazon/Meta?
Dynamic programming counting problems like this appear frequently in interviews at companies such as Amazon, Google, and Meta. Variations often involve dice, coin change, or ways to reach a target sum using constrained choices.
What data structure is used in Number of Dice Rolls With Target Sum?
The main data structure is a dynamic programming table or memoization cache indexed by dice count and remaining sum. Implementations usually use a 2D array or dictionary for memoization and sometimes reduce space to a 1D array.
What is the time complexity of Number of Dice Rolls With Target Sum?
The optimal dynamic programming solution runs in O(n * k * target) time. There are n dice states and up to target sums, and each state iterates through k possible face values. Space complexity is typically O(n * target), which can be optimized to O(target).