You are given coins of different denominations and a total amount of money amount. Write a function to compute 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.

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

Note:
You may assume that you have an infinite number of each kind of coin.

思路

dp[i] = min(dp[i], dp[i-c] + 1)

Python

1
2
3
4
5
6
7
8
def coinChange(coins, amount):
dp = [0] + [float('inf') for i in range(amount)]

for i in range(1, amount+1):
for c in coins:
if c <= i:
dp[i] = min(dp[i], dp[i-c] + 1)
return -1 if dp[amount] > amount else dp[amount]

Golang

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func coinChange(coins []int, amount int) int {
dp := make([]int, amount+1)

for i := 1; i <= amount; i++ {
dp[i] = amount + 1
}

for i := 0; i<=amount; i++ {
for _, c := range(coins) {
if i >= c && dp[i] > dp[i-c] + 1 {
dp[i] = dp[i-c] + 1
}
}
}

if dp[amount] > amount {
return -1
}

return dp[amount]
}

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
pub fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
let mut dp: Vec<i32> = vec![0; (amount+1) as usize];
for i in 1..amount+1 {
dp[i as usize] = amount + 1;
}

for i in 0..amount+1{
coins.iter().for_each(|c|
if(*c <= i && dp[i as usize] > dp[(i - *c) as usize] + 1) {
dp[i as usize] = dp[(i - *c) as usize] + 1
}
);
}

if dp[amount as usize] > amount {
return -1;
} else {
return dp[amount as usize];
}
}

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int coinChange(int* coins, int coinsSize, int amount){
float POS_INF = 1.0 / 0.0;
float dp[amount+1];
for (int i=0; i<=amount; i++){
dp[i] = (i == 0) ? 0 : POS_INF;
}

for (int i=1; i<=amount; i++) {
for (int j=0; j<coinsSize; j++) {
int c = coins[j];
if (c <= i && (float)dp[i] > dp[i-c] + 1) {
dp[i] = dp[i-c] + 1;
}
}
}

return dp[amount] > (float)amount ? -1 : (int)dp[amount];
}

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int coinChange(int[] coins, int amount) {
double dp[] = new double[amount+1];

for (int i=0; i<=amount; i++) {
dp[i] = i == 0 ? 0 : Double.POSITIVE_INFINITY;
}

for (int i=1; i<=amount; i++) {
for (int c: coins) {
if (c <= i && dp[i] > dp[i-c] + 1) {
dp[i] = dp[i-c] + 1;
}
}
}

return dp[amount] > amount ? -1 : (int)dp[amount];
}

Javascript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var coinChange = function(coins, amount) {
var dp = new Array();
for (var i=0; i<=amount; i++){
dp[i] = (i == 0) ? 0 : Infinity;
}

for (var i=1; i<=amount; i++) {
coins.forEach(c => {
if (c <= i) {
dp[i] = Math.min(dp[i], dp[i - c] + 1)
}
})
}
return dp[amount] > amount ? -1 : dp[amount]
};

Submissions

Reference 参考

[1] 322. Coin Change