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

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(aim == 0) return 0 ;
        //f[i]表示，对于价值i的最少找零货币数目
        int f[] = new int[aim + 1]  ;
        for(int i = 0 ; i <= aim ; i ++) {//每种价值
            f[i] = Integer.MAX_VALUE ;//表示每个面值都默认不能被找零
            for(int j = 0 ; j < arr.length ; j ++) {//每种货币
                if(arr[j] == i) {//如果价值就等于当前货币的面值，那么只需要一张即可
                    f[i] = 1 ;
                    continue ;
                } 
                //如果当前货币小于价值，则可以假设已经找零当前货币，剩下的价值继续
                //寻找最小货币数目
                if(arr[j] < i) {
                    if(f[i-arr[j]] != Integer.MAX_VALUE) {//只有剩下的价值可以被找零才进行考虑
                        f[i] = Math.min(f[i] , f[i-arr[j]] + 1) ;    
                    }
                }
               
            }
        }
        return f[aim] == Integer.MAX_VALUE ? -1 : f[aim] ;  
    }
}