Number of dice rolls with target sum

Dynamic Programming

62.2% acceptance

Feb 25, 2026

5318

186

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.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn num_rolls_to_target(n: i32, k: i32, target: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let (n, k, t) = (n as usize, k as usize, target as usize);
    let mut dp = vec![0i64; t + 1];
    dp[0] = 1;
    for _ in 0..n {
      let mut next = vec![0i64; t + 1];
      for j in 0..=t {
        if dp[j] == 0 { continue; }
        for f in 1..=k {
          if j + f <= t {
            next[j + f] = (next[j + f] + dp[j]) % MOD;
          }
        }
      }
      dp = next;
    }
    dp[t] as i32
  }
}