Breadth-First Search
Array
Dynamic Programming
Description
You are given an integer array coins
representing coins of different denominations and an integer amount
representing a total amount of money.
Return the fewest number of coins that you need to make up that amount . If that amount of money cannot be made up by any combination of the coins, return -1
.
You may assume that you have an infinite number of each kind of coin.
Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3
Output: -1
Example 3:
Input: coins = [1], amount = 0
Output: 0
Constraints:
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
Solutions
Solution 1: Dynamic Programming (Complete Knapsack)
We define $f[i][j]$ as the minimum number of coins needed to make up the amount $j$ using the first $i$ types of coins. Initially, $f[0][0] = 0$, and the values of other positions are all positive infinity.
We can enumerate the quantity $k$ of the last coin used, then we have:
$$
f[i][j] = \min(f[i - 1][j], f[i - 1][j - x] + 1, \cdots, f[i - 1][j - k \times x] + k)
$$
where $x$ represents the face value of the $i$-th type of coin.
Let $j = j - x$, then we have:
$$
f[i][j - x] = \min(f[i - 1][j - x], f[i - 1][j - 2 \times x] + 1, \cdots, f[i - 1][j - k \times x] + k - 1)
$$
Substituting the second equation into the first one, we can get the following state transition equation:
$$
f[i][j] = \min(f[i - 1][j], f[i][j - x] + 1)
$$
The final answer is $f[m][n]$.
The time complexity is $O(m \times n)$, and the space complexity is $O(m \times n)$. Where $m$ and $n$ are the number of types of coins and the total amount, respectively.
Python3 Java C++ Go TypeScript Rust JavaScript
class Solution :
def coinChange ( self , coins : List [ int ], amount : int ) -> int :
m , n = len ( coins ), amount
f = [[ inf ] * ( n + 1 ) for _ in range ( m + 1 )]
f [ 0 ][ 0 ] = 0
for i , x in enumerate ( coins , 1 ):
for j in range ( n + 1 ):
f [ i ][ j ] = f [ i - 1 ][ j ]
if j >= x :
f [ i ][ j ] = min ( f [ i ][ j ], f [ i ][ j - x ] + 1 )
return - 1 if f [ m ][ n ] >= inf else f [ m ][ n ]
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 coinChange ( int [] coins , int amount ) {
final int inf = 1 << 30 ;
int m = coins . length ;
int n = amount ;
int [][] f = new int [ m + 1 ][ n + 1 ] ;
for ( var g : f ) {
Arrays . fill ( g , inf );
}
f [ 0 ][ 0 ] = 0 ;
for ( int i = 1 ; i <= m ; ++ i ) {
for ( int j = 0 ; j <= n ; ++ j ) {
f [ i ][ j ] = f [ i - 1 ][ j ] ;
if ( j >= coins [ i - 1 ] ) {
f [ i ][ j ] = Math . min ( f [ i ][ j ] , f [ i ][ j - coins [ i - 1 ]] + 1 );
}
}
}
return f [ m ][ n ] >= inf ? - 1 : f [ m ][ n ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 class Solution {
public :
int coinChange ( vector < int >& coins , int amount ) {
int m = coins . size (), n = amount ;
int f [ m + 1 ][ n + 1 ];
memset ( f , 0x3f , sizeof ( f ));
f [ 0 ][ 0 ] = 0 ;
for ( int i = 1 ; i <= m ; ++ i ) {
for ( int j = 0 ; j <= n ; ++ j ) {
f [ i ][ j ] = f [ i - 1 ][ j ];
if ( j >= coins [ i - 1 ]) {
f [ i ][ j ] = min ( f [ i ][ j ], f [ i ][ j - coins [ i - 1 ]] + 1 );
}
}
}
return f [ m ][ n ] > n ? -1 : f [ m ][ n ];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 func coinChange ( coins [] int , amount int ) int {
m , n := len ( coins ), amount
f := make ([][] int , m + 1 )
const inf = 1 << 30
for i := range f {
f [ i ] = make ([] int , n + 1 )
for j := range f [ i ] {
f [ i ][ j ] = inf
}
}
f [ 0 ][ 0 ] = 0
for i := 1 ; i <= m ; i ++ {
for j := 0 ; j <= n ; j ++ {
f [ i ][ j ] = f [ i - 1 ][ j ]
if j >= coins [ i - 1 ] {
f [ i ][ j ] = min ( f [ i ][ j ], f [ i ][ j - coins [ i - 1 ]] + 1 )
}
}
}
if f [ m ][ n ] > n {
return - 1
}
return f [ m ][ n ]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 function coinChange ( coins : number [], amount : number ) : number {
const m = coins . length ;
const n = amount ;
const f : number [][] = Array ( m + 1 )
. fill ( 0 )
. map (() => Array ( n + 1 ). fill ( 1 << 30 ));
f [ 0 ][ 0 ] = 0 ;
for ( let i = 1 ; i <= m ; ++ i ) {
for ( let j = 0 ; j <= n ; ++ j ) {
f [ i ][ j ] = f [ i - 1 ][ j ];
if ( j >= coins [ i - 1 ]) {
f [ i ][ j ] = Math . min ( f [ i ][ j ], f [ i ][ j - coins [ i - 1 ]] + 1 );
}
}
}
return f [ m ][ n ] > n ? - 1 : f [ m ][ n ];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 impl Solution {
pub fn coin_change ( coins : Vec < i32 > , amount : i32 ) -> i32 {
let n = amount as usize ;
let mut f = vec! [ n + 1 ; n + 1 ];
f [ 0 ] = 0 ;
for & x in & coins {
for j in x as usize ..= n {
f [ j ] = f [ j ]. min ( f [ j - ( x as usize )] + 1 );
}
}
if f [ n ] > n {
- 1
} else {
f [ n ] as i32
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 /**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function ( coins , amount ) {
const m = coins . length ;
const n = amount ;
const f = Array ( m + 1 )
. fill ( 0 )
. map (() => Array ( n + 1 ). fill ( 1 << 30 ));
f [ 0 ][ 0 ] = 0 ;
for ( let i = 1 ; i <= m ; ++ i ) {
for ( let j = 0 ; j <= n ; ++ j ) {
f [ i ][ j ] = f [ i - 1 ][ j ];
if ( j >= coins [ i - 1 ]) {
f [ i ][ j ] = Math . min ( f [ i ][ j ], f [ i ][ j - coins [ i - 1 ]] + 1 );
}
}
}
return f [ m ][ n ] > n ? - 1 : f [ m ][ n ];
};
We notice that $f[i][j]$ is only related to $f[i - 1][j]$ and $f[i][j - x]$. Therefore, we can optimize the two-dimensional array into a one-dimensional array, reducing the space complexity to $O(n)$.
Similar problems:
Python3 Java C++ Go TypeScript JavaScript
class Solution :
def coinChange ( self , coins : List [ int ], amount : int ) -> int :
n = amount
f = [ 0 ] + [ inf ] * n
for x in coins :
for j in range ( x , n + 1 ):
f [ j ] = min ( f [ j ], f [ j - x ] + 1 )
return - 1 if f [ n ] >= inf else f [ n ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 class Solution {
public int coinChange ( int [] coins , int amount ) {
final int inf = 1 << 30 ;
int n = amount ;
int [] f = new int [ n + 1 ] ;
Arrays . fill ( f , inf );
f [ 0 ] = 0 ;
for ( int x : coins ) {
for ( int j = x ; j <= n ; ++ j ) {
f [ j ] = Math . min ( f [ j ] , f [ j - x ] + 1 );
}
}
return f [ n ] >= inf ? - 1 : f [ n ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 class Solution {
public :
int coinChange ( vector < int >& coins , int amount ) {
int n = amount ;
int f [ n + 1 ];
memset ( f , 0x3f , sizeof ( f ));
f [ 0 ] = 0 ;
for ( int x : coins ) {
for ( int j = x ; j <= n ; ++ j ) {
f [ j ] = min ( f [ j ], f [ j - x ] + 1 );
}
}
return f [ n ] > n ? -1 : f [ n ];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 func coinChange ( coins [] int , amount int ) int {
n := amount
f := make ([] int , n + 1 )
for i := range f {
f [ i ] = 1 << 30
}
f [ 0 ] = 0
for _ , x := range coins {
for j := x ; j <= n ; j ++ {
f [ j ] = min ( f [ j ], f [ j - x ] + 1 )
}
}
if f [ n ] > n {
return - 1
}
return f [ n ]
}
function coinChange ( coins : number [], amount : number ) : number {
const n = amount ;
const f : number [] = Array ( n + 1 ). fill ( 1 << 30 );
f [ 0 ] = 0 ;
for ( const x of coins ) {
for ( let j = x ; j <= n ; ++ j ) {
f [ j ] = Math . min ( f [ j ], f [ j - x ] + 1 );
}
}
return f [ n ] > n ? - 1 : f [ n ];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 /**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function ( coins , amount ) {
const n = amount ;
const f = Array ( n + 1 ). fill ( 1 << 30 );
f [ 0 ] = 0 ;
for ( const x of coins ) {
for ( let j = x ; j <= n ; ++ j ) {
f [ j ] = Math . min ( f [ j ], f [ j - x ] + 1 );
}
}
return f [ n ] > n ? - 1 : f [ n ];
};