Leetcode322. 零钱兑换
题目描述
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1：
1
2
3
| 输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
|
示例 2：
1
2
| 输入：coins = [2], amount = 3
输出：-1
|
示例 3：
1
2
| 输入：coins = [1], amount = 0
输出：0
|
示例 4：
1
2
| 输入：coins = [1], amount = 1
输出：1
|
示例 5：
1
2
| 输入：coins = [1], amount = 2
输出：2
|
提示：
- 1≤coins.length≤12
- 1≤coins[i]≤231−1
- 0≤amount≤104
解题思路
这道题无疑需要用动态规划的思想去做，问题是怎么实现。
方法一：记忆化搜索（自顶向下）
假设我们用函数f(x)来表示凑成金额x所需的最少硬币数，那么我们可以很容易地得出下述的一个公式：
f(x)=min(f(x−coins[0]),f(x−coins[1]),⋯,f(x−coins[coins.size()−1]))+1
根据这个公式，我们已经可以写出递归暴力的方法了。然后我们用记忆化搜索的方法来优化一下，用一个dp数组来记录已经算出来的值来避免重复计算。
具体的算法细节见下述代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| vector<int>dp;
int dfs(int amount,vector<int>& coins)
{
if(amount<0) return -1;
if(amount==0) return 0;
if(dp[amount]!=0) return dp[amount];
int minSum=INT32_MAX;
for(int i=0;i<coins.size();++i)
{
int t=dfs(amount-coins[i],coins);
if(t>=0&&t<minSum) minSum=t+1;
}
dp[amount]=minSum==INT32_MAX?-1:minSum;
return dp[amount];
}
int coinChange(vector<int>& coins, int amount)
{
if(amount<1) return 0;
dp.resize(amount+1);
return dfs(amount,coins);
}
|
时间复杂度：O(Sn)，其中 S 是金额，n是面额数。
空间复杂度：O(S)，其中 S 是金额。
方法二：动态规划（自底向上）
有了方法一中的公式，我们可以用动态规划的思想来实现它。
具体的实现细节见下述代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int coinChange(vector<int>& coins, int amount)
{
if(amount<1) return 0;
int maxSum=amount+2;
vector<int>dp(amount+1,maxSum);
dp[0]=0;
for(int i=1;i<=amount;++i)
{
for(int j=0;j<coins.size();++j)
{
if(i>=coins[j])
{
dp[i]=min(dp[i],dp[i-coins[j]]+1);
}
}
}
return dp[amount]>amount?-1:dp[amount];
}
|
PS: 因为有对dp中元素加1的操作，如果将dp中元素初始化为INF32_MAX会发生溢出！
时间复杂度：O(Sn)，其中 S 是金额，n是面额数。
空间复杂度：O(S)，其中 S 是金额。
虽然两种方法的时空复杂度是一样的，但是记忆化搜索的方法运行更高效。
