凑齐钱的最小张数概念：
比如只有2块、3块和5块钱若干，问凑齐100块钱最小需要几张钱能凑齐？（20张5块的，所以是20张）
前面一篇求解编辑距离时，有现成的状态转移方程，可是这种凑齐面值的没有现成的公式，只能自己去推导。
当然我们可以利用求余数求解，凑齐98块，需要98/5=19…3,所以为19张5块+1张3块（一共20张）
但这个可能用余数可能更方便，但对于动态归划方法，可能是个思路
比如只有2、3、7块，用表格推导的过程如下：
而如果只有2、5、9块，它的推导如下：
根据推导过程，写出的算法如下：
public class Lesson10_1 {
// 钱币币种可选的值，自己可随意改
private static final int[] coins = {2, 5, 9};
// 如果不加变量保存，每次都要重复递归计算
private static Map<Integer, Integer> hasCount = new HashMap<>();
// 传入总金额和可选币种，返回凑够该金额的最小数量，返回null表示没有找到
// 为null表示凑不齐这个钱（商场买菜要1块钱，可选币种最小值要2块，我们不能傻得给人家2块不找零，此时就是凑不齐）
public static Integer getCount(int total, int[] coins) {
// 如果之前已计算过该金额的，直接返回，无需递归调用了
if (hasCount.containsKey(total)) {
return hasCount.get(total);
}
// 递归减到了负数，也没凑齐，就是没找到
if (total < 0) {
return null;
} else if (total == 0) {// 金额为0，那需要的数量肯定为0
return 0;
} else {
int length = coins.length;
// 保存可选币种中，每种所需的最小数量
Integer[] min = new Integer[length];
for (int i = 0; i < length; i++) {
// 比如求凑20块钱，可选值是5块钱，那递归求凑15块+1即可 C20(5) = C15(5) + 1
// 再比如求凑18块钱，可选值2块钱，那递归求凑16块+1即可 C18(2) = C16(2) + 1
// C n (m) = C n-m (m) + 1
Integer tmpResult = getCount(total - coins[i], coins);
// 返回值为空，说明递归调用到 if (total < 0) 时返回了空，没有凑够该值
min[i] = tmpResult != null ? (tmpResult + 1) : null;
}
// 去除空值
List<Integer> resultList = Arrays.stream(min).filter(e -> e != null).collect(Collectors.toList());
// 如果不为空，那最小值就是所需的最小个数
Integer result = resultList.size() > 0 ? resultList.stream().mapToInt(e -> e).min().getAsInt() : null;
// 放到map中，防止后续重复递归计算
hasCount.put(total, result);
return result;
}
}
public static void main(String[] args) {
Integer count = getCount(102, coins);
System.out.println(count);
}
}