江苏龙网

  1. 首页 > 生活 > >

动态规划和贪心法的区别( 三 )


取最小值，需要三个硬币

（8）面值为8时，两个方案：
① 比1元（一个硬币）多了7元（三个硬币），需要四个硬币
② 比5元（一个硬币）多了3元（三个硬币），需要四个硬币
取最小值，需要四个硬币

（9）面值为9时，两个方案：
① 比1元（一个硬币）多了8元（四个硬币），需要五个硬币
② 比5元（一个硬币）多了4元（四个硬币），需要五个硬币
取最小值，需要五个硬币

（10）面值为10时，两个方案：
① 比1元（一个硬币）多了9元（五个硬币），需要六个硬币
② 比5元（一个硬币）多了5元（一个硬币），需要两个硬币
取最小值，需要两个硬币

（11）面值为11时，三个方案：
① 比1元（一个硬币）多了10元（两个硬币），需要三个硬币
② 比5元（一个硬币）多了6元（两个硬币），需要三个硬币
③ 取面值为11元的硬币，需要一个硬币
取最小值，需要一个硬币

（12）面值为12时，三个方案：
① 比1元（一个硬币）多了11元（一个硬币），需要两个硬币
② 比5元（一个硬币）多了7元（三个硬币），需要四个硬币
③ 比11元（一个硬币）多了1元（一个硬币），需要两个硬币
取最小值，需要两个硬币

（11）面值为13时，三个方案：
① 比1元（一个硬币）多了12元（两个硬币），需要三个硬币
② 比5元（一个硬币）多了8元（四个硬币），需要五个硬币
③ 比11元（一个硬币）多了2元（两个硬币），需要三个硬币
取最小值，需要三个硬币

（14）面值为14时，三个方案：
① 比1元（一个硬币）多了13元（三个硬币），需要四个硬币
② 比5元（一个硬币）多了9元（五个硬币），需要六个硬币
③ 比11元（一个硬币）多了3元（三个硬币），需要四个硬币
取最小值，需要四个硬币

（15）面值为15时，三个方案：
① 比1元（一个硬币）多了14元（四个硬币），需要五个硬币
② 比5元（一个硬币）多了10元（两个硬币），需要三个硬币
③ 比11元（一个硬币）多了4元（四个硬币），需要五个硬币
取最小值，需要三个硬币

（16）最终，得到的最小硬币数是3。并且从推导过程可以看出，计算一个数额的最少硬币数，比如15，必须把它前面的所有数额（1~14）的最少硬币数都计算出来。这够成了一个递推（注意不是递归）的过程。

上述推导过程的Java实现：
```
public class CoinDP {

/**
* 动态规划算法
* @param values:\t 保存所有币值的数组
* @param valueKinds:硬币种类
* @param money:\t 金额
* @param minCoins: 保存所有金额所需的最小硬币数
*/
public static void dp(int values, int money, int minCoins) {

\t\tint valueKinds = values.length;
minCoins = 0;
// 保存1元、2元、3元、……、money元所需的最小硬币数
for (int sum = 1; sum \u0026lt;= money; sum++) {

// 使用最小币值，需要的硬币数量是最多的
int min = sum;

// 遍历每一种面值的硬币
for (int kind = 0; kind \u0026lt; valueKinds; kind++) {
// 若当前面值的硬币小于总额则分解问题并查表
if (values \u0026lt;= sum) {
int temp = minCoins] + 1;
if (temp \u0026lt; min) {
min = temp;


推荐阅读


上一篇：魔兽世界的兽人语、鱼人语是怎样设计出来的

下一篇：Apple Music上线半年付费用户1000万，是否可超越Spotify