GuilinDev
Lc0322
05 August 2008
322 Coin Change
原题
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:
1
2
3
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:
1
2
Input: coins = [2], amount = 3
Output: -1
Note:
You may assume that you have an infinite number of each kind of coin.
分析
一维DP，top down和bottom up两种方法，需要特别掌握bottom up递推方法和相应的空间优化。
DP方程和递归树
这道题是完全背包问题的变种，采用动态规划维护一个二维数组dp，dp[i][j]表示从第1个元素到第i个元素累计总金额为j时的最少硬币数量，递推公式为：
1
dp[i]= min(dp[i], dp[i − coins[j]] + 1)
意思是当零钱为 i 元需要的最少硬币数 = min (啥也不干 or 第i元 - 硬币中所有出现的可能小于i元的硬币的出现次数 + 1)。
代码
bottom up，没法状态压缩
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) {
// dp[i] - 当金额为i时，所需的最少coins;
// dp[i] = min(dp[i - coin] + 1, dp[i])，要么选择当前coin，coin数+1，要么不选择，coin数不变
// dp[amount]
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0; // 0元需要0个硬币
for (int i = 0; i < dp.length; i++) {
for (int coin : coins) {
if (i - coin < 0) {
continue;
}
dp[i] = Math.min(dp[i - coin] + 1, dp[i]);
}
}
// 如果dp[amount] == amount + 1，说明没有组合的硬币
return (dp[amount] == amount + 1) ? -1 : dp[amount];
}
}
另一种写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
for (int i = 1; i <= amount; i++) {
dp[i] = amount + 1; //初始化每个位置，不能到达，dp[0]为凑满0元，可以达到
}
// 转移方程
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1); // 选择当前coin或者不选择
}
}
}
if (dp[amount] > amount) { // 当前amount没有组合的硬币
return -1;
}
return dp[amount];
}
}
topdown
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public int coinChange(int[] coins, int amount) {
int[] memo = new int[amount + 1]; // memo[i]表示记录凑齐i块钱需要的coin数目
Arrays.fill(memo, -100); // 随便来个负数做初始化，-1是找不到硬币组合需要返回的值，所以这里用-1之外任何负数代表初始化没有组合
memo[0] = 0; // 0块钱需要0个硬币
return coinChange(coins, amount, memo);
}
private int coinChange(int[] coins, int amount, int[] memo) {
if (amount < 0) { // not valid
return -1;
}
if (amount == 0) { // 已完成
return 0;
}
if (memo[amount] != -100) { //剪枝，之前已经计算过
return memo[amount];
}
for (int coin : coins) {// 对比选择当前硬币coins[i]或者不选择
if (coin > amount) {
continue;
}
int option = coinChange(coins, amount - coin, memo);
if (option == -1) { // 递归返回的是not valid，直接跳过本次组合
continue;
}
if (memo[amount] == -100 || option + 1 < memo[amount]) {
memo[amount] = option + 1;
}
}
if (memo[amount] == -100) {
memo[amount] = -1;
}
return memo[amount];
}
}