第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0518. 零钱兑换 II

题目地址(518. 零钱兑换 II)

题目描述

1
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
2
3
示例 1:
4
5
输入: amount = 5, coins = [1, 2, 5]
6
输出: 4
7
解释: 有四种方式可以凑成总金额:
8
5=5
9
5=2+2+1
10
5=2+1+1+1
11
5=1+1+1+1+1
12
示例 2:
13
14
输入: amount = 3, coins = [2]
15
输出: 0
16
解释: 只用面额 2 的硬币不能凑成总金额 3。
17
示例 3:
18
19
输入: amount = 10, coins = [10]
20
输出: 1
21
22
注意:
23
24
你可以假设:
25
26
0 <= amount (总金额) <= 5000
27
1 <= coin (硬币面额) <= 5000
28
硬币种类不超过 500 种
29
结果符合 32 位符号整数
Copied!

前置知识

公司

  • 阿里
  • 百度
  • 字节

思路

这个题目和 coin-change 的思路比较类似。
进一步我们可以对问题进行空间复杂度上的优化(这种写法比较难以理解,但是相对更省空间)
用 dp[i] 来表示组成 i 块钱,需要最少的硬币数,那么
  1. 1.
    第 j 个硬币我可以选择不拿 这个时候, 组成数 = dp[i]
  2. 2.
    第 j 个硬币我可以选择拿 这个时候, 组成数 = dp[i - coins[j]] + dp[i]
  3. 3.
    和 01 背包问题不同, 硬币是可以拿任意个,属于完全背包问题
  4. 4.
    对于每一个 dp[i] 我们都选择遍历一遍 coin, 不断更新 dp[i]
eg:
1
if (amount === 0) return 1;
2
3
const dp = [Array(amount + 1).fill(1)];
4
5
for (let i = 1; i < amount + 1; i++) {
6
dp[i] = Array(coins.length + 1).fill(0);
7
for (let j = 1; j < coins.length + 1; j++) {
8
// 从1开始可以简化运算
9
if (i - coins[j - 1] >= 0) {
10
// 注意这里是coins[j -1]而不是coins[j]
11
dp[i][j] = dp[i][j - 1] + dp[i - coins[j - 1]][j]; // 由于可以重复使用硬币所以这里是j不是j-1
12
} else {
13
dp[i][j] = dp[i][j - 1];
14
}
15
}
16
}
17
18
return dp[dp.length - 1][coins.length];
Copied!
  • 当我们选择一维数组去解的时候,内外循环将会对结果造成影响
eg:
1
// 这种答案是不对的。
2
// 原因在于比如amount = 5, coins = [1,2,5]
3
// 这种算法会将[1,2,2] [2,1,2] [2, 2, 1] 算成不同的
4
5
if (amount === 0) return 1;
6
7
const dp = [1].concat(Array(amount).fill(0));
8
9
for (let i = 1; i < amount + 1; i++) {
10
for (let j = 0; j < coins.length; j++) {
11
if (i - coins[j] >= 0) {
12
dp[i] = dp[i] + dp[i - coins[j]];
13
}
14
}
15
}
16
17
return dp[dp.length - 1];
18
19
// 正确的写法应该是内外循环调换一下, 具体可以看下方代码区
Copied!

关键点解析

  • 动态规划

代码

代码支持:Python3,JavaScript:
JavaSCript Code:
1
/*
2
* @lc app=leetcode id=518 lang=javascript
3
*
4
* [518] Coin Change 2
5
*
6
*/
7
/**
8
* @param {number} amount
9
* @param {number[]} coins
10
* @return {number}
11
*/
12
var change = function (amount, coins) {
13
if (amount === 0) return 1;
14
15
const dp = [1].concat(Array(amount).fill(0));
16
17
for (let j = 0; j < coins.length; j++) {
18
for (let i = 1; i < amount + 1; i++) {
19
if (i - coins[j] >= 0) {
20
dp[i] = dp[i] + dp[i - coins[j]];
21
}
22
}
23
}
24
25
return dp[dp.length - 1];
26
};
Copied!
Python Code:
1
class Solution:
2
def change(self, amount: int, coins: List[int]) -> int:
3
dp = [0] * (amount + 1)
4
dp[0] = 1
5
6
for j in range(len(coins)):
7
for i in range(1, amount + 1):
8
if i >= coins[j]:
9
dp[i] += dp[i - coins[j]]
10
11
return dp[-1]
Copied!
复杂度分析
  • 时间复杂度:$O(amount)$
  • 空间复杂度:$O(amount * len(coins))$

扩展 1

这是一道很简单描述的题目, 因此很多时候会被用到大公司的电面中。
相似问题:

扩展 2

Python 二维解法(不推荐,但是可以帮助理解):
1
class Solution:
2
def change(self, amount: int, coins: List[int]) -> int:
3
dp = [[0 for _ in range(len(coins) + 1)] for _ in range(amount + 1)]
4
for j in range(len(coins) + 1):
5
dp[0][j] = 1
6
7
for i in range(amount + 1):
8
for j in range(1, len(coins) + 1):
9
if i >= coins[j - 1]:
10
dp[i][j] = dp[i - coins[j - 1]][j] + dp[i][j - 1]
11
else:
12
dp[i][j] = dp[i][j - 1]
13
return dp[-1][-1]
Copied!
复杂度分析
  • 时间复杂度:$O(amount * len(coins))$
  • 空间复杂度:$O(amount * len(coins))$
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。