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

java-
因为每种货币的数量无限制使用，所以为完全背包问题。

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 len = arr.length;
        int[] dp = new int[aim+1];
        // 用Integer.MAX_VALUE/2填充，是为了防止数值溢出
        Arrays.fill(dp, Integer.MAX_VALUE/2);
        dp[0] = 0;
        // 外层遍历物品
        for(int i = 0; i < arr.length; i++){
            // 内层从该物品大小遍历到背包容量大小
            for(int j = arr[i]; j <= aim; j++){
                dp[j] = Math.min(dp[j], dp[j-arr[i]]+1);
            }
        }
        if(dp[aim]>=Integer.MAX_VALUE/2) return -1;
        return dp[aim];
    }
}