Welcome to Subscribe On Youtube
1155. Number of Dice Rolls With Target Sum
Description
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
Solutions
Solution 1: 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)$.
Solution 2
This implementation uses dynamic programming. It traverses the relevant values and updates its state as each value is processed. After all required states have been considered, the maintained result is returned.
-
class Solution { public int numRollsToTarget(int n, int k, int target) { final int mod = (int) 1e9 + 7; int[][] f = new int[n + 1][target + 1]; f[0][0] = 1; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= Math.min(target, i * k); ++j) { for (int h = 1; h <= Math.min(j, k); ++h) { f[i][j] = (f[i][j] + f[i - 1][j - h]) % mod; } } } return f[n][target]; } } // Solution 2 class Solution { public int numRollsToTarget(int n, int k, int target) { final int mod = (int) 1e9 + 7; int[] f = new int[target + 1]; f[0] = 1; for (int i = 1; i <= n; ++i) { int[] g = new int[target + 1]; for (int j = 1; j <= Math.min(target, i * k); ++j) { for (int h = 1; h <= Math.min(j, k); ++h) { g[j] = (g[j] + f[j - h]) % mod; } } f = g; } return f[target]; } } -
class Solution { public: int numRollsToTarget(int n, int k, int target) { const int mod = 1e9 + 7; int f[n + 1][target + 1]; memset(f, 0, sizeof f); f[0][0] = 1; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= min(target, i * k); ++j) { for (int h = 1; h <= min(j, k); ++h) { f[i][j] = (f[i][j] + f[i - 1][j - h]) % mod; } } } return f[n][target]; } }; // Solution 2 class Solution { public: int numRollsToTarget(int n, int k, int target) { const int mod = 1e9 + 7; vector<int> f(target + 1); f[0] = 1; for (int i = 1; i <= n; ++i) { vector<int> g(target + 1); for (int j = 1; j <= min(target, i * k); ++j) { for (int h = 1; h <= min(j, k); ++h) { g[j] = (g[j] + f[j - h]) % mod; } } f = move(g); } return f[target]; } }; -
class Solution: def numRollsToTarget(self, n: int, k: int, target: int) -> int: f = [[0] * (target + 1) for _ in range(n + 1)] f[0][0] = 1 mod = 10**9 + 7 for i in range(1, n + 1): for j in range(1, min(i * k, target) + 1): for h in range(1, min(j, k) + 1): f[i][j] = (f[i][j] + f[i - 1][j - h]) % mod return f[n][target] # Solution 2 class Solution: def numRollsToTarget(self, n: int, k: int, target: int) -> int: f = [1] + [0] * target mod = 10**9 + 7 for i in range(1, n + 1): g = [0] * (target + 1) for j in range(1, min(i * k, target) + 1): for h in range(1, min(j, k) + 1): g[j] = (g[j] + f[j - h]) % mod f = g return f[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] } // Solution 2 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] } -
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]; } // Solution 2 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]; } -
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] } } // Solution 2 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] } }