手写代码：有三种面值的硬币k1 < k2 < k3 ，找k面值的零钱，最少需要多少硬币

Answer 1

参考回答：

假设有1 元，3 元，5 元的硬币，假设一个函数 d(i) 来表示需要凑出 i 的总价值需要的最少硬币数量。

当i = 0 时， d(0) = 0。不需要凑零钱，当然也不需要任何硬币了。

当i = 1 时，因为有 1 元的硬币，所以直接在第 1 步的基础上，加上 1 个 1 元硬币，得出 d(1) = 1。

当i = 2 时，因为并没有 2 元的硬币，所以只能拿 1 元的硬币来凑。在第 2 步的基础上，加上 1 个 1 元硬币，得出 d(2) = 2。

当i = 3 时，可以在第 3 步的基础上加上 1 个 1 元硬币，得到 3 这个结果。但其实有 3 元硬币，所以这一步的最优结果不是建立在第 3 步的结果上得来的，而是应该建立在第 1 步上，加上 1 个 3 元硬币，得到 d(3) = 1。

除了第1 步这个看似基本的公理外，其他往后的结果都是建立在它之前得到的某一步的最优解上，加上 1 个硬币得到。得出：

d(i) = d(j) + 1

这里j < i。通俗地讲，我们需要凑出 i 元，就在凑出 j 的结果上再加上某一个硬币就行了。

那这里我们加上的是哪个硬币呢。嗯，其实很简单，把每个硬币试一下就行了：

• 假设最后加上的是1 元硬币，那 d(i) = d(j) + 1 = d(i - 1) + 1。

• 假设最后加上的是3 元硬币，那 d(i) = d(j) + 1 = d(i - 3) + 1。

• 假设最后加上的是5 元硬币，那 d(i) = d(j) + 1 = d(i - 5) + 1。

我们分别计算出d(i - 1) + 1，d(i - 3) + 1，d(i - 5) + 1 的值，取其中的最小值，即为最优解，也就是 d(i)。

最后公式：

 

代码示例：

public class CoinProblemBasicTest {

private int[] d; // 储存结果

private int[] coins = {1, 3, 5}; // 硬币种类

private void d_func(int i, int num) {
if (i == 0) {
d[i] = 0;
d_func(i + 1, num);
}
else {
int min = 9999999;
for (int coin : coins) {
if (i >= coin && d[i - coin] + 1 < min) {
min = d[i - coin] + 1;
}
}
d[i] = min;
if (i < num) {
d_func(i + 1, num);
}
}
}
public void test() throws Exception {

int sum = 11; // 需要凑 11 元

d = new int[sum + 1]; // 初始化数组

d_func(0, sum); // 计算需要凑出 0 ～ sum 元需要的硬币数量

for (int i = 0; i <= sum; i++) {

System.out.println("凑齐 " + i + " 元需要 " + d[i] + " 个硬币");

}

}

}