题解 | #兑换零钱(一),记忆化递归#

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] ;
    }
}