Array
Dynamic Programming
Description
You have an infinite number of coins with values 1, 2, and 6, and only 2 coins with value 4.
Given an integer n
, return the number of ways to make the sum of n
with the coins you have.
Since the answer may be very large, return it modulo 109 + 7
.
Note that the order of the coins doesn't matter and [2, 2, 3]
is the same as [2, 3, 2]
.
Example 1:
Input: n = 4
Output: 4
Explanation:
Here are the four combinations: [1, 1, 1, 1]
, [1, 1, 2]
, [2, 2]
, [4]
.
Example 2:
Input: n = 12
Output: 22
Explanation:
Note that [4, 4, 4]
is not a valid combination since we cannot use 4 three times.
Example 3:
Input: n = 5
Output: 4
Explanation:
Here are the four combinations: [1, 1, 1, 1, 1]
, [1, 1, 1, 2]
, [1, 2, 2]
, [1, 4]
.
Constraints:
Solutions
Solution 1: Dynamic Programming (Complete Knapsack)
We can start by ignoring coin $4$, defining the coin array coins = [1, 2, 6]
, and then using the idea of the complete knapsack problem. We define $f[j]$ as the number of ways to make up amount $j$ using the first $i$ types of coins, initially $f[0] = 1$. Then, we iterate through the coin array coins
, and for each coin $x$, we iterate through amounts from $x$ to $n$, updating $f[j] = f[j] + f[j - x]$.
Finally, $f[n]$ is the number of ways to make up amount $n$ using coins $1, 2, 6$. Then, if $n \geq 4$, we consider choosing one coin $4$, so the number of ways becomes $f[n] + f[n - 4]$, and if $n \geq 8$, we consider choosing two coins $4$, so the number of ways becomes $f[n] + f[n - 4] + f[n - 8]$.
Note the modulus operation for the answer.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the amount.
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 class Solution :
def numberOfWays ( self , n : int ) -> int :
mod = 10 ** 9 + 7
coins = [ 1 , 2 , 6 ]
f = [ 0 ] * ( n + 1 )
f [ 0 ] = 1
for x in coins :
for j in range ( x , n + 1 ):
f [ j ] = ( f [ j ] + f [ j - x ]) % mod
ans = f [ n ]
if n >= 4 :
ans = ( ans + f [ n - 4 ]) % mod
if n >= 8 :
ans = ( ans + f [ n - 8 ]) % mod
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 class Solution {
public int numberOfWays ( int n ) {
final int mod = ( int ) 1e9 + 7 ;
int [] coins = { 1 , 2 , 6 };
int [] f = new int [ n + 1 ] ;
f [ 0 ] = 1 ;
for ( int x : coins ) {
for ( int j = x ; j <= n ; ++ j ) {
f [ j ] = ( f [ j ] + f [ j - x ] ) % mod ;
}
}
int ans = f [ n ] ;
if ( n >= 4 ) {
ans = ( ans + f [ n - 4 ] ) % mod ;
}
if ( n >= 8 ) {
ans = ( ans + f [ n - 8 ] ) % mod ;
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 class Solution {
public :
int numberOfWays ( int n ) {
const int mod = 1e9 + 7 ;
int coins [ 3 ] = { 1 , 2 , 6 };
int f [ n + 1 ];
memset ( f , 0 , sizeof ( f ));
f [ 0 ] = 1 ;
for ( int x : coins ) {
for ( int j = x ; j <= n ; ++ j ) {
f [ j ] = ( f [ j ] + f [ j - x ]) % mod ;
}
}
int ans = f [ n ];
if ( n >= 4 ) {
ans = ( ans + f [ n - 4 ]) % mod ;
}
if ( n >= 8 ) {
ans = ( ans + f [ n - 8 ]) % mod ;
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 func numberOfWays ( n int ) int {
const mod int = 1e9 + 7
coins := [] int { 1 , 2 , 6 }
f := make ([] int , n + 1 )
f [ 0 ] = 1
for _ , x := range coins {
for j := x ; j <= n ; j ++ {
f [ j ] = ( f [ j ] + f [ j - x ]) % mod
}
}
ans := f [ n ]
if n >= 4 {
ans = ( ans + f [ n - 4 ]) % mod
}
if n >= 8 {
ans = ( ans + f [ n - 8 ]) % mod
}
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 function numberOfWays ( n : number ) : number {
const mod = 10 ** 9 + 7 ;
const f : number [] = Array ( n + 1 ). fill ( 0 );
f [ 0 ] = 1 ;
for ( const x of [ 1 , 2 , 6 ]) {
for ( let j = x ; j <= n ; ++ j ) {
f [ j ] = ( f [ j ] + f [ j - x ]) % mod ;
}
}
let ans = f [ n ];
if ( n >= 4 ) {
ans = ( ans + f [ n - 4 ]) % mod ;
}
if ( n >= 8 ) {
ans = ( ans + f [ n - 8 ]) % mod ;
}
return ans ;
}
Solution 2: Preprocessing + Dynamic Programming (Complete Knapsack)
We can start by preprocessing the number of ways to make up every amount from $1$ to $10^5$, and then return the corresponding number of ways based on the value of $n$:
If $n < 4$, directly return $f[n]$;
If $4 \leq n < 8$, return $f[n] + f[n - 4]$;
If $n \geq 8$, return $f[n] + f[n - 4] + f[n - 8]$.
Note the modulus operation for the answer.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the amount.
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 m = 10 ** 5 + 1
mod = 10 ** 9 + 7
coins = [ 1 , 2 , 6 ]
f = [ 0 ] * ( m )
f [ 0 ] = 1
for x in coins :
for j in range ( x , m ):
f [ j ] = ( f [ j ] + f [ j - x ]) % mod
class Solution :
def numberOfWays ( self , n : int ) -> int :
ans = f [ n ]
if n >= 4 :
ans = ( ans + f [ n - 4 ]) % mod
if n >= 8 :
ans = ( ans + f [ n - 8 ]) % mod
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 class Solution {
private static final int MOD = 1000000007 ;
private static final int M = 100001 ;
private static final int [] COINS = { 1 , 2 , 6 };
private static final int [] f = new int [ M ] ;
static {
f [ 0 ] = 1 ;
for ( int x : COINS ) {
for ( int j = x ; j < M ; ++ j ) {
f [ j ] = ( f [ j ] + f [ j - x ] ) % MOD ;
}
}
}
public int numberOfWays ( int n ) {
int ans = f [ n ] ;
if ( n >= 4 ) {
ans = ( ans + f [ n - 4 ] ) % MOD ;
}
if ( n >= 8 ) {
ans = ( ans + f [ n - 8 ] ) % MOD ;
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 const int m = 1e5 + 1 ;
const int mod = 1e9 + 7 ;
int f [ m + 1 ];
auto init = [] {
f [ 0 ] = 1 ;
int coins [ 3 ] = { 1 , 2 , 6 };
for ( int x : coins ) {
for ( int j = x ; j < m ; ++ j ) {
f [ j ] = ( f [ j ] + f [ j - x ]) % mod ;
}
}
return 0 ;
}();
class Solution {
public :
int numberOfWays ( int n ) {
int ans = f [ n ];
if ( n >= 4 ) {
ans = ( ans + f [ n - 4 ]) % mod ;
}
if ( n >= 8 ) {
ans = ( ans + f [ n - 8 ]) % mod ;
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 const (
m = 100001
mod = 1000000007
)
var f [ m ] int
func init () {
f [ 0 ] = 1
coins := [] int { 1 , 2 , 6 }
for _ , x := range coins {
for j := x ; j < m ; j ++ {
f [ j ] = ( f [ j ] + f [ j - x ]) % mod
}
}
}
func numberOfWays ( n int ) int {
ans := f [ n ]
if n >= 4 {
ans = ( ans + f [ n - 4 ]) % mod
}
if n >= 8 {
ans = ( ans + f [ n - 8 ]) % mod
}
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 const m : number = 10 ** 5 + 1 ;
const mod : number = 10 ** 9 + 7 ;
const f : number [] = Array ( m ). fill ( 0 );
(() => {
f [ 0 ] = 1 ;
const coins : number [] = [ 1 , 2 , 6 ];
for ( const x of coins ) {
for ( let j = x ; j < m ; ++ j ) {
f [ j ] = ( f [ j ] + f [ j - x ]) % mod ;
}
}
})();
function numberOfWays ( n : number ) : number {
let ans = f [ n ];
if ( n >= 4 ) {
ans = ( ans + f [ n - 4 ]) % mod ;
}
if ( n >= 8 ) {
ans = ( ans + f [ n - 8 ]) % mod ;
}
return ans ;
}
GitHub