Dynamic Programming
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 <= 30
1 <= 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)$.
Python3 Java C++ Go TypeScript Rust
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 ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 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 ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 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 ];
}
};
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
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 ]
}
1
2
3
4
5
6
7
8
9
10
11
12
13 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 ];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 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
Python3 Java C++ Go TypeScript Rust
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 ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 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 ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 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 ];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 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 ]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 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 ];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 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 ]
}
}
GitHub