题解 | #兑换零钱(一)#
兑换零钱(一)
https://www.nowcoder.com/practice/3911a20b3f8743058214ceaa099eeb45
package com.hhdd.dp;
import java.util.HashSet;
import java.util.Set;
/**
* 给定数组arr，arr中所有的值都为正整数且不重复。
* 每个值代表一种面值的货币，每种面值的货币可以使用任意张
* ，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
*
* @Author huanghedidi
* @Date 2022/8/4 22:44
*/
public class 兑换零钱 {
public static void main(String[] args) {
int[] arr = new int[]{357, 322, 318, 181, 22, 158, 365};
int aim = 4976;
int res = minMoney(arr, aim);
System.out.println("res = " + res);
}
/**
* dp[i]代表组成i最少需要的货币数
*
* @param arr
* @param aim
* @return
*/
public static int minMoney(int[] arr, int aim) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i < arr.length; i++) {
set.add(arr[i]);
}
int[] dp = new int[aim + 1];
// 0的位置默认就是0
dp[0] = 0;
// 其他位置默认设置成一个超大数字
for (int i = 1; i <= aim; i++) {
dp[i] = 99999;
}
// write code here
for (int i = 1; i <= aim; i++) {
boolean findFlg = false;
for (int j = 0; j < i; j++) {
// 只有当规模小到可以直接在set中查到结果才可接受
int tmp = i - j;
// 字典中包含，且j位置不是-1才代表加上这个零钱后可以完整兑换
// 并取出较小值，因为前面时候可能存储过值
if (set.contains(tmp) && dp[j] != -1) {
findFlg = true;
dp[i] = Math.min(dp[j] + 1, dp[i]);
}
}
// 从来没有找到过，就把该位置设置成-1
if (!findFlg) {
dp[i] = -1;
}
}
return dp[aim];
}
}