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 number of combinations that make up that amount . If that amount of money cannot be made up by any combination of the coins, return 0
.
You may assume that you have an infinite number of each kind of coin.
The answer is guaranteed to fit into a signed 32-bit integer.
Example 1:
Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
Example 2:
Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.
Example 3:
Input: amount = 10, coins = [10]
Output: 1
Constraints:
1 <= coins.length <= 300
1 <= coins[i] <= 5000
All the values of coins
are unique .
0 <= amount <= 5000
Solutions
Solution 1: Dynamic Programming (Complete Knapsack)
We define $f[i][j]$ as the number of coin combinations to make up the amount $j$ using the first $i$ types of coins. Initially, $f[0][0] = 1$, and the values of other positions are all $0$.
We can enumerate the quantity $k$ of the last coin used, then we have equation one:
$$
f[i][j] = f[i - 1][j] + f[i - 1][j - x] + f[i - 1][j - 2 \times x] + \cdots + f[i - 1][j - k \times x]
$$
where $x$ represents the face value of the $i$-th type of coin.
Let $j = j - x$, then we have equation two:
$$
f[i][j - x] = f[i - 1][j - x] + f[i - 1][j - 2 \times x] + \cdots + f[i - 1][j - k \times x]
$$
Substituting equation two into equation one, we can get the following state transition equation:
$$
f[i][j] = f[i - 1][j] + f[i][j - x]
$$
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
class Solution :
def change ( self , amount : int , coins : List [ int ]) -> int :
m , n = len ( coins ), amount
f = [[ 0 ] * ( n + 1 ) for _ in range ( m + 1 )]
f [ 0 ][ 0 ] = 1
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 ] += f [ i ][ j - x ]
return f [ m ][ n ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 class Solution {
public int change ( int amount , int [] coins ) {
int m = coins . length , n = amount ;
int [][] f = new int [ m + 1 ][ n + 1 ] ;
f [ 0 ][ 0 ] = 1 ;
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 ] += f [ i ][ j - coins [ i - 1 ]] ;
}
}
}
return 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 change ( int amount , vector < int >& coins ) {
int m = coins . size (), n = amount ;
unsigned f [ m + 1 ][ n + 1 ];
memset ( f , 0 , sizeof ( f ));
f [ 0 ][ 0 ] = 1 ;
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 ] += f [ i ][ j - coins [ i - 1 ]];
}
}
}
return f [ m ][ n ];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 func change ( amount int , coins [] int ) int {
m , n := len ( coins ), amount
f := make ([][] int , m + 1 )
for i := range f {
f [ i ] = make ([] int , n + 1 )
}
f [ 0 ][ 0 ] = 1
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 ] += f [ i ][ j - coins [ i - 1 ]]
}
}
}
return f [ m ][ n ]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14 function change ( amount : number , coins : number []) : number {
const [ m , n ] = [ coins . length , amount ];
const f : number [][] = Array . from ({ length : m + 1 }, () => Array ( n + 1 ). fill ( 0 ));
f [ 0 ][ 0 ] = 1 ;
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 ] += f [ i ][ j - coins [ i - 1 ]];
}
}
}
return 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)$.
Python3 Java C++ Go TypeScript
class Solution :
def change ( self , amount : int , coins : List [ int ]) -> int :
n = amount
f = [ 1 ] + [ 0 ] * n
for x in coins :
for j in range ( x , n + 1 ):
f [ j ] += f [ j - x ]
return f [ n ]
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution {
public int change ( int amount , int [] coins ) {
int n = amount ;
int [] f = new int [ n + 1 ] ;
f [ 0 ] = 1 ;
for ( int x : coins ) {
for ( int j = x ; j <= n ; ++ j ) {
f [ j ] += f [ j - x ] ;
}
}
return f [ n ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 class Solution {
public :
int change ( int amount , vector < int >& coins ) {
int n = amount ;
unsigned 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 - x ];
}
}
return f [ n ];
}
};
func change ( amount int , coins [] int ) int {
n := amount
f := make ([] int , n + 1 )
f [ 0 ] = 1
for _ , x := range coins {
for j := x ; j <= n ; j ++ {
f [ j ] += f [ j - x ]
}
}
return f [ n ]
}
function change ( amount : number , coins : number []) : number {
const n = amount ;
const f : number [] = Array ( n + 1 ). fill ( 0 );
f [ 0 ] = 1 ;
for ( const x of coins ) {
for ( let j = x ; j <= n ; ++ j ) {
f [ j ] += f [ j - x ];
}
}
return f [ n ];
}
GitHub