题解 | #换钱的最少货币数#

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) {
        // write code here
        int length = arr.length;
        if(length == 0){//空数组处理
            return -1;
        }
        
        int[] dp = new int[aim+1];//创建一个动态规划dp数组，dp[i]表示兑换面额为i的最少货币数量。
        Arrays.fill(dp,aim+1);//初始化dp数组为最大值(根据题意可以是大于aim的任意整数)
        dp[0] = 0;//换面额为0的最少货币数量位0
        for(int i=1;i<=aim;i++){//迭代更新dp[i]数组
            for(int j = 0;j<length;j++){//遍历所有面额值
                if(i>=arr[j]){
                    //动态规划关系式，dp[i] = min(dp[i], dp[i-arr[j]] +1);,利用前面已经求得的数据（dp[i-arr[j]]）更新dp[i]
                    dp[i] = Math.min(dp[i],dp[i-arr[j]]+1);
                }
            }
        }
        
        //返回值，如果dp[aim]>aim表示不能兑换，反之可以兑换，且最少兑换货币数量为dp[aim]
        return dp[aim]>aim?-1:dp[aim];
    }
}