题目描述
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
提示：
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
解法
方法一：动态规划(完全背包)
我们定义 $f[i][j]$ 表示使用前 $i$ 种硬币，凑出金额 $j$ 的最少硬币数。初始时 $f[0][0] = 0$，其余位置的值均为正无穷。
我们可以枚举使用的最后一枚硬币的数量 $k$，那么有：
$$
f[i][j] = \min(f[i - 1][j], f[i - 1][j - x] + 1, \cdots, f[i - 1][j - k \times x] + k)
$$
其中 $x$ 表示第 $i$ 种硬币的面值。
不妨令 $j = j - x$，那么有：
$$
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)
$$
将二式代入一式，我们可以得到以下状态转移方程：
$$
f[i][j] = \min(f[i - 1][j], f[i][j - x] + 1)
$$
最后答案即为 $f[m][n]$。
时间复杂度 $O(m \times n)$，空间复杂度 $O(m \times n)$。其中 $m$ 和 $n$ 分别为硬币的种类数和总金额。
| 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];
};
|
我们注意到 $f[i][j]$ 只与 $f[i - 1][j]$ 和 $f[i][j - x]$ 有关，因此我们可以将二维数组优化为一维数组，空间复杂度降为 $O(n)$。
相似题目：
| 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];
};
|