牛客网面试必刷：CD12 换钱的最少货币数

前言

问题链接: CD12 换钱的最少货币数

一、动态规划

参考自：【编程题 动态规划】兑换零钱(一)（详细注释 易懂）

解题思想：

具体思想就是（还是以上面的举例为例），我先设定，凑0元钱，只用0张钱；然后我要凑一元钱，去面值里面找，没有合适的；然后凑两元钱，还是没有合适的；凑三元，没有合适的；凑四元，4-4=0，我就看凑0元 需要几张钱，发现是0张，那凑4元，就是在原有基础上加1，也就是需要1张钱；凑5元，5-4=1，发现凑1元，没有明确的张数，那再看面值5元的，5-5=0，那依然是需要0+1=1张；凑6元，6-4=2，没有明确的张数，6-5=1，也没有；凑7元，7-4=3，没有明确的张数，7-5=2，也没有明确的张数；凑8元，8-4=4，我们看到凑四元需要1张，那凑8元就是2张，8-5=3，没有明确的张数；凑9元，9-4=5，需要1+1=2张，9-5=4，需要1+1=2张，凑够9元有两种方案，选最少的张数，这里都是2，所以就保留2；凑10元，10-4=6，没有明确的张数，10-5=5，需要1+1=2；凑11元，11-4=7，没有明确的张数，11-5=6，也没有；凑12元，12-4=8，需要2+1=3张，12-5=7，没有明确的张数；凑13元，13-4=9，需要2+1=3，13-5=8，需要2+1=3，选最少的张数，就是3； 最后看要凑的钱数里面，就是看凑13元里面，有多少张钱数，那怎么判断呢？ 最后凑13元，钱的张数如果小于等于13元，那就是对的，因为可能有面值1元的。 所以，上面提到的 没有明确的张数，我们可以设置为 13+1=14，这样如果你被凑到了就一定会小于等于 13元，反之就大于13元。

（1）需要判断钱币和总金额

 public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int amt = in.nextInt();int[] arr = new int[n];for(int i=0;i<n;i++){arr[i] = in.nextInt();}int[] dp = new int[amt+1];Arrays.fill(dp,amt+1);dp[0] = 0;//很重要，一定要设置dp[0]=0，这是起点！for(int i = 1; i <= amt ;i++){for(int j = 0; j < n ; j++){if(i>=arr[j]){//如果arr[j]>i，说明钱包里的这张钱已经大于需要拼凑的金额，无法用来拼凑,需要忽略，否则索引越界！dp[i] = Math.min(dp[i],dp[i-arr[j]]+1);}}}System.out.println(dp[amt]>amt?-1:dp[amt]);}

（2）不需要判断钱币和总金额

import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int amt = in.nextInt();int[] arr = new int[n];for(int i=0;i<n;i++){arr[i] = in.nextInt();}int[] dp = new int[amt+1];Arrays.fill(dp,amt+1);dp[0] = 0;for (int i = 1 ; i <= n ; i++) {for (int j = arr[i - 1] ; j <= amt ; j++) {dp[j] = Math.min(dp[j], dp[j - arr[i - 1]] + 1);}}System.out.println(dp[amt]>amt?-1:dp[amt]);}
}