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[] dp = new int[aim+1];
Arrays.fill(dp,aim+1);
dp[0] = 0;
for(int i = 1;i<=aim;i++){
for(int coin:arr){
if(i-coin<0){
continue;
}
dp[i] = Math.min(dp[i],dp[i-coin]+1);
}
}
return dp[aim] == aim+1 ? -1:dp[aim];
}
}