Coins: Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (1 cent), write code to calculate the number of ways of representing n cents.
Hints: #300, #324, #343, #380, #394
解法1（审题错误）
你有25分、10分、5分、1分面值的硬币，给一个n让你求有几种能够组合能够变成n。
举个例子：
n=34，求Coins(34)（求34的各种组合）。
先从第一个硬币开始，如果我选择的1分，那么结果就是1分 + C(33)。如果选择的是5分，那么结果就是5分 + C(29)，其他情况以此类推。
需要注意的是因为是组合问题不是排列问题，因此要避免得到重复结果，比如{1, 1, 1, 1, 5, 25}和{5, 1, 25, 1, 1, 1}是一样的。
解决办法是选择的硬币的面值必须 >= 上一个硬币的面值
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
39
40
41
42
43
44
45
46
47
48
49
50
|
public List<List<Integer>> coins(int n) {
List<Integer> sofar = new ArrayList<>();
sofar.add(0);
List<List<Integer>> result = new ArrayList<>();
coins(sofar, 0, n, result);
return result;
}
public void coins(List<Integer> sofar, int currentSum, int targetSum, List<List<Integer>> result) {
if (currentSum == targetSum) {
result.add(sofor.subList(1));
return;
}
if (currentSum > targetSum) {
return;
}
int lastCoin = getLast(sofar);
if (1 >= lastCoin) {
add(sofar, 1);
coins(sofar, currentSum + 1, targetSum, result);
removeLast(sofar);
}
if (5 >= lastCoin) {
add(sofar, 1);
coins(sofar, currentSum + 5, targetSum, result);
removeLast(sofar);
}
if (10 >= lastCoin) {
add(sofar, 1);
coins(sofar, currentSum + 5, targetSum, result);
removeLast(sofar);
}
if (25 >= lastCoin) {
add(sofar, 1);
coins(sofar, currentSum + 5, targetSum, result);
removeLast(sofar);
}
}
private add(List<Integer> list, Integer i) {
list.add(i);
}
private getLast(List<Integer> list) {
return list.get(list.size() - 1);
}
private removeLast(List<Integer> list) {
return list.remove(list.size() - 1);
}
|
解法2
题目要求的计算有多少种方式，而不是求出所有方式。
选择第一个硬币的数量，我们从大到小选，先选25分面值的硬币，假设目标是100分：
1
2
3
4
5
|
F(100) = F(100分, 用0个25分)
+ F(100分, 用1个25分)
+ F(100分, 用2个25分)
+ F(100分, 用3个25分)
+ F(100分, 用4个25分)
|
25硬币的使用情况都已经枚举完毕，后面是10分硬币的情况。注意到：
1
2
3
4
5
|
F(100分, 用0个25分) = F(100分, 用0..n个10分)
F(100分, 用1个25分) = F(75分, 用0..n个10分)
F(100分, 用2个25分) = F(50分, 用0..n个10分)
F(100分, 用3个25分) = F(25分, 用0..n个10分)
F(100分, 用4个25分) = F(0分，用0..n个10分) = 1
|
然后再选5分硬币，比如：
1
|
F(100分, 用1个10分) = F(90分, 用0..n个5分)
|
最后选1分硬币，比如：
1
|
F(90分, 用1个5分) = F(85, 用0..n个1分) = 1
|
Base Condition有2个：
- 到当选用1分硬币的时候你就只有1种选择，因为你只能全部用1分。
- 当总金额为0的时候你也就只有1种选择。
代码：
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
|
public int coins(int amount) {
return coins(amount, 25);
}
public int coins(int amount, int currentMianzhi) {
if (currentMianzhi == 1) {
return 1;
}
if (amount == 0) {
return 1;
}
int ways = 0;
for (int i = 0; i * currentMianzhi <= amount; i++) {
int remainingAmount = amount - i * currentMianzhi;
int nextMianzhi = getNextMianzhi(currentMianzhi);
ways += coins(remainingAmount, nextMianzhi);
}
return ways;
}
private int getNextMianzhi(int mianzhi) {
if (mianzhi == 25) {
return 10;
}
if (mianzhi == 10) {
return 5;
}
if (mianzhi == 5) {
return 1;
}
return 0;
}
|
不过上面的做法对于每次取下一个面值代码有点写死，可以这样做：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public int coins(int amount) {
int[] mianzhi = new int[] {25, 10, 5, 1};
return coins(amount, mianzhis, 0);
}
public int coins(int amount, int[] mianzhis, int mianzhiIndex) {
if (mianzhiIndex == mianzhis.length - 1) {
// 已经是最小面值了，在本题中是1
return 1;
}
int ways = 0;
int mianzhi = mianzhis[mianzhiIndex];
for (int i = 0; i * mianzhi <= amount; i++) {
int remainingAmount = amount - i * mianzhi;
ways += coins(remainingAmount, mianzhis, mianzhiIndex + 1);
}
return ways;
}
|
解法3
上面的做法里存在重复计算：
1
2
3
4
|
F(100) = F(100分, 用0个25分) = F(100, 用0..n个10分)
+ ...
+ F(100分, 用2个25分) = F(50, 用0..n个10分)
+ ...
|
而：
1
2
3
4
5
|
F(100, 用0..n个10分) = F(100, 0个10分)
+ ...
+ F(100, 5个10分) = F(50, 0..n个5分)
F(50, 用0..n个10分) = F(50, 0个10分) = F(50, 0..n个5分)
+ ...
|
可以看到存在重复计算。
也就是说F(总金额,面值)可以作为key来缓存结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public int coins(int amount) {
int[] mianzhi = new int[] {25, 10, 5, 1};
int[][] cache = new int[mianzhi.length][amount + 1];
return coins(amount, mianzhis, 0, cache);
}
public int coins(int amount, int[] mianzhis, int mianzhiIndex, int[][] cache) {
if (cache[mianzhiIndex][amount] != 0) {
return cache[mianzhiIndex][amount];
}
if (mianzhiIndex == mianzhis.length - 1) {
return 1;
}
int ways = 0;
int mianzhi = mianzhis[mianzhiIndex];
for (int i = 0; i * mianzhi <= amount; i++) {
int remainingAmount = amount - i * mianzhi;
ways += coins(remainingAmount, mianzhis, mianzhiIndex + 1);
}
cache[mianzhiIndex][amount] = ways;
return ways;
}
|
评论