找零问题：需找零金额为w，硬币面值有(d1, d2, d3，…，dm)，最少需要多少枚硬币。
问题：需找零金额为8，硬币面值有(1, 3, 2, 5)，最少需要多少枚硬币。
设f(j)表示总金额为j时最少的零钱数，f(0) = 0，w表示找零金额，有零钱一堆{d1, d2, d3，…，dm}。同样根据之前的经验，要达到为j，那么必然是j – di(1 <= i <= m)面值的硬币数再加1个di面值的硬币，当然j >= di，即f(j) = f(j - di) + 1, j >= di。
java
 1 package com.algorithm.dynamicprogramming; 2  3 import java.util.arrays; 4  5 /** 6  * 找零问题 7  * created by yulinfeng on 7/5/17. 8  */ 9 public class money {10     public static void main(string[] args) {11         int[] money = {1, 3, 2, 5};12         int sum = 8;13         int count = money(money, sum);14         system.out.println(count);15     }16 17     private static int money(int[] money, int sum) {18         int[] count = new int[sum + 1];19         count[0] = 0;20         for (int j = 1; j < sum + 1; j++) { //总金额数，1,2,3，……，sum21 int mincoins = j;22 for (int i = 0; i < money.length; i++) { //遍历硬币的面值23 if (j - money[i] >= 0) {24                     int temp = count[j - money[i]] + 1; //当前所需硬币数25                     if (temp < mincoins) {26 mincoins = temp;27 }28 }29 }30 31 count[j] = mincoins;32 }33 system.out.println(arrays.tostring(count));34 return count[sum];35 }36 }
python3
1 #coding=utf-8 2 def charge_making(money, num): 3 ''' 4 找零问题 5 ''' 6 count = [0] * (num + 1) 7 count[0] = 0 8 for j in range(1, num + 1): 9 mincoins = j10 for i in range(len(money)):11 if j - money[i] >= 0:12                 temp = count[j - money[i]] + 113                 if temp < mincoins:14                     mincoins = temp15         16         count[j] = mincoins17     18     return count[num]19 20 money = [1, 3, 2, 5]21 num = 822 count = charge_making(money, num)23 print(count)
tag
以上就是动态规划之找零问题详解的详细内容。