题解 | #兑换零钱(一)#

import java.util.*;

public class Solution { /** * 最少货币数 * @param arr int整型一维数组 the array * @param aim int整型 the target * @return int整型 / int res=Integer.MAX_VALUE; public int minMoney (int[] arr, int aim) { if(arr.length==0) return -1; // write code here Arrays.sort(arr); getRes(arr,aim,0,arr.length-1); return res==Integer.MAX_VALUE?-1:res; } public void getRes(int[] arr, int aim,int count,int index){ if(index<0) return; for(int i=(aim/arr[index]);i>=0;--i){ int result=aim-iarr[index]; int newCount = count + i; if(result==0){ res=Math.min(res,newCount); break; } if (newCount + 1 >= res) break; getRes(arr,result,newCount,index-1); } } }