题解 | #找零#

java版——完全背包
把购买完商品剩余的钱看作背包容量，把硬币看作物品，硬币的面值看作物品重量，物品的价值就是硬币数，本题要求最小硬币数，所以我们要让价值尽可能小。

public class Main{
    public static void main(String[] args){
        Scanner cin = new Scanner(System.in);
        int N = cin.nextInt();
        int n = 1024 - N;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        int[] coin = {1, 4, 16, 64};
        for(int i = 0; i < coin.length; i++){
            for(int j = coin[i]; j <= n; j++){
                dp[j] = Math.min(dp[j], dp[j - coin[i]] + 1);
            }
        }
        System.out.println(dp[n]);
    }
}