1155. Number of Dice Rolls With Target Sum

You have d dice, and each die has f faces numbered 1, 2, ..., f.

Return the number of possible ways (out of fd total ways) modulo 10^9 + 7 to roll the dice so the sum of the face up numbers equals target.

 

Example 1:

Input: d = 1, f = 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: d = 2, f = 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: d = 2, f = 5, target = 10
Output: 1
Explanation: 
You throw two dice, each with 5 faces.  There is only one way to get a sum of 10: 5+5.

Example 4:

Input: d = 1, f = 2, target = 3
Output: 0
Explanation: 
You throw one die with 2 faces.  There is no way to get a sum of 3.

Example 5:

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

 

Constraints:

  • 1 <= d, f <= 30
  • 1 <= target <= 1000

Rust Solution

struct Solution;

use std::collections::HashMap;

impl Solution {
    fn num_rolls_to_target(d: i32, f: i32, target: i32) -> i32 {
        let mut memo: HashMap<(i32, i32), i32> = HashMap::new();
        Self::dp(d, f, target, &mut memo)
    }

    fn dp(d: i32, f: i32, target: i32, memo: &mut HashMap<(i32, i32), i32>) -> i32 {
        if let Some(&val) = memo.get(&(d, target)) {
            return val;
        }
        let res = if d == 0 {
            if target == 0 {
                1
            } else {
                0
            }
        } else {
            let mut sum = 0;
            for i in 1..=f {
                sum += Self::dp(d - 1, f, target - i, memo);
                sum %= 1_000_000_007;
            }
            sum
        };
        memo.insert((d, target), res);
        res
    }
}

#[test]
fn test() {
    let d = 1;
    let f = 6;
    let target = 3;
    let res = 1;
    assert_eq!(Solution::num_rolls_to_target(d, f, target), res);
    let d = 2;
    let f = 6;
    let target = 7;
    let res = 6;
    assert_eq!(Solution::num_rolls_to_target(d, f, target), res);
    let d = 2;
    let f = 5;
    let target = 10;
    let res = 1;
    assert_eq!(Solution::num_rolls_to_target(d, f, target), res);
    let d = 1;
    let f = 2;
    let target = 3;
    let res = 0;
    assert_eq!(Solution::num_rolls_to_target(d, f, target), res);
    let d = 30;
    let f = 30;
    let target = 500;
    let res = 222_616_187;
    assert_eq!(Solution::num_rolls_to_target(d, f, target), res);
}

Having problems with this solution? Click here to submit an issue on github.