题解 | 兑换零钱(一)

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
        if (aim <= 0){
            return 0;
        }
        int[]dp = new int[aim + 1];

        dp[0] = 0;
        for (int i = 1; i < dp.length; i ++){
            dp[i] = 100000;
        }

        for (int i = 1 ; i < dp.length; i ++){
            for (int j = 0; j < arr.length; j ++){
                if (i - arr[j] < 0){
                    continue;
                }
                dp[i] = Math.min(dp[i], dp[i - arr[j]] + 1);
            }
        }

        return dp[aim] > aim ? -1 : dp[aim];
    }
}

经典完全背包问题，核心：dp[i] = Math.min(dp[i], dp[i - arr[j]] + 1);

假设是面额是arr[5，3，2]，目标是7元

x = 无穷大

dp 中的第n位代表n元所需的最少面额张数，n=0,0元不需要面额。

dp = [0 x x x x x x x]

n = 1，面额比1大，跳过

n = 2，遍历arr,只有2-2 = 0，2元加dp[0] + 1份：dp = [0 x 1 x x x x x]

n = 3，遍历arr，

一：3 - 3 = 0，3元加dp[0] + 1份 = 1

二：3 - 2 = 1，2元加dp[1] + 1份 = x + 1

Math.min(一，二) = 一：dp = [0 x 1 1 x x x x]

以此类推