最近在LeetCode上刷算法题，准备秋招。刷了一些题之后，发现有些题非常棒，能够将多种知识点结合在一起。本文就以“零钱兑换”问题为例，展示同一道题的多种不同解法。
零钱兑换问题
原题中文版链接：https://leetcode-cn.com/problems/coin-change/
原题英文版链接：https://leetcode.com/problems/coin-change/
解法1：贪心法 + BFS
贪心法的思路是每次都优先选择可以选择的最大面额的硬币。
比如硬币的面额分别是：[1, 2, 5]；需要兑换的零钱是：11。
按照贪心法的思路，优先选择 2个面额为 5 的硬币，然后剩下的零钱是 11 - 2 * 5 = 1。然后再选择 1 个面额为 1 的硬币，剩下的零钱是 1 - 1 * 1 = 0。解决问题！最终得到的结果是 3。可以验证答案是正确的！
贪心法的思路很直观，而且大部分情况下能够正确解决问题。但可惜对于某些特殊情况，贪心法得到的答案是错误的。
比如硬币的面额分别是：[1, 7, 10]；需要兑换的零钱是：14。
按照贪心法的思路，优先选择 1 个面额为 10 的硬币，然后剩下的零钱是 14 - 10 = 4，只能选择 4 个面额为 1 的硬币。最终得到的结果是需要 5 个硬币。可以验证，这不是正确答案。正确答案是选择 2 个面额为 7 的硬币。
贪心法思路简单、直接，但不能保证答案是正确的。那贪心法就没有了吗？能不能想想办法，保证使用贪心法时能够找到正确答案呢？有的！答案就是：贪心法 + 深度优先搜索（DFS）。
我们可以使用贪心法的思想，每次优先选择可能的最大面额的硬币。但在此之上，为了保证得到正确解，我们需要按深度优先搜索的方法，遍历整个递归状态树。不过，我们可以加上一些剪枝条件，加快搜索速度。
具体解法如下：
C++解法：
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if (amount <= 0 || coins.empty()) return 0;
// 对币值按照从大到小的顺序排序
sort(coins.rbegin(), coins.rend());
int ans = INT_MAX;
backtrack(coins, amount, 0, 0, ans);
return ans == INT_MAX ? -1 : ans;
}
private:
void backtrack(vector<int> &coins, int amount, int idx, int count, int & ans) {
// 递归终止条件
if (amount == 0) {
ans = min(count, ans); // 保证得到的是正确答案
return;
}
if (idx == coins.size()) return;
// count + k < ans 剪枝条件
for (int k = amount / coins[idx]; k >= 0 && count + k < ans; k--)
// k * coins[idx] 加快搜索速度
backtrack(coins, amount - k * coins[idx], idx + 1, count + k, ans);
}
};
Python解法
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
if amount <= 0 or not coins: return 0
// 对币值按照从大到小的顺序排序
coins.sort(reverse=True)
self.res = amount + 1
self.dfs(coins, amount, 0, 0)
return -1 if self.res == amount + 1 else self.res
def dfs(self, coins, amount, idx, count):
// 递归终止条件
if amount == 0:
self.res = min(self.res, count) // 保证得到的是正确答案
return
if idx >= len(coins):
return
k = amount // coins[idx]
// count + k < ans 剪枝条件
while k >= 0 and count + k < self.res:
// k * coins[idx] 加快搜索速度
self.dfs(coins, amount - k * coins[idx], idx + 1, count + k)
k -= 1
参考题解：https://leetcode-cn.com/problems/coin-change/solution/322-by-ikaruga/
解法2：动态规划
动态规划是这道题最常见的解法。利用递归的思想，要想知道凑成零钱 amount 的最少硬币数量，只需要知道所有 amount - coin[i] 对应的零钱需要的最少硬币数量，然后求出最少的那个数量再加上 1 即可。然后因为中间的零钱数量可能重复，因此需要采用一个数组保存中间结果。具体解法如下：
Python
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
if amount <= 0: return 0
# dp 数组存储中间结果，初始化为最大值
dp = [(amount + 1)] * (amount + 1)
dp[0] = 0
# 从 1 开始计算各个零钱数需要的硬币数量
for i in range(1, amount + 1):
for c in coins:
if i - c >= 0:
dp[i] = min(dp[i], dp[i - c] + 1)
return -1 if dp[-1] == amount + 1 else dp[-1]
解法3：广度优先搜索
除了以上两种解法，我们还可以使用广度优先搜索（BFS）。如下图所示，我们可以将零钱根据硬币面额展开成一棵多叉树，其中多叉树的每个分支对应硬币的面额。然后使用广度优先搜索，当扩展出来的节点值为 0 时，表示已经完成兑换，多叉树当前的层次就是结果。
零钱根据Coin面额展开的多叉树
Python
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
if amount <= 0: return 0
count = 0
# 从 amount 开始递减
value1, value2 = [amount], []
visited = [False] * amount + [True]
while value1:
count += 1
for val in value1:
for coin in coins:
newval = val - coin
if newval >= 0:
if not visited[newval]:
# 终止条件
if newval == 0:
return count
visited[newval] = True
value2.append(newval)
value1, value2 = value2, []
return -1
Python
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
if amount <= 0: return 0
count = 0
# 从 0 开始累加
value1, value2 = [0], []
visited = [True] + [False] * amount
while value1:
count += 1
for val in value1:
for coin in coins:
newval = val + coin
if newval <= amount:
if not visited[newval]:
# 终止条件
if newval == amount:
return count
visited[newval] = True
value2.append(newval)
value1, value2 = value2, []
return -1
参考题解：https://leetcode.com/problems/coin-change/discuss/77361/Fast-Python-BFS-Solution
综上所述，解决零钱兑换问题，至少有3种完全不同的解法。其中跟动态规划紧密相连的“递归+记忆化”解法在此并未提及。递归解法是自顶向下的思路，动态规划的自底向上的思路，两者殊途同归。不过可以看出，最常见的动态规划解法其实并不是最优的。以我的提交情况来看，“贪心法+DFS”优于 BFS，BFS 优于动态规划。
你还能想到什么其他解法，欢迎评论交流。
网友评论