import java.util.*; public class Solution { /** * 最少货币数 * @param arr int整型一维数组 the array * @param aim int整型 the target * @return int整型 */ public int minMoney (int[] arr, int aim) { if(arr == null || arr.length == 0) return -1 ; int f[] = new int[aim+1] ;//f[i]表示价值i的最少找零货币数目 return help(arr , aim , f) ; } public int help(int arr[] , int aim , int f[]) { if(aim == 0) return 0 ; if(aim < 0) return -1 ; if(f[aim] != 0) return f[aim] ;//如果为零说明还未计算,不为零说明已经计算 int min = -1 ;//当前价值的最小货币数,-1表示无法找零 for(int i = 0 ; i < arr.length ; i ++) {//遍历每一种货币 int tmp = help(arr , aim - arr[i] , f) ; if(tmp != -1) {//可以找零 if(min == -1) {//是默认值 min = tmp + 1 ; } else { min = Math.min(min , tmp + 1) ; } } f[aim] = min ;//更新f[] } return f[aim] ; } }