找零问题

Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币，以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为的商品，请问最少他会收到多少硬币？

解析1：数学方法。%为取余，/为取商

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int total = 1024;
        int cost = sc.nextInt();//总容量
        int a = (total - cost)/64;//12
        int b = ((total - cost)%64)/16;//3
        int c = (((total - cost)%64)%16)/4;
        int d = (((total - cost)%64)%16%4)/1;
        System.out.println(a+b+c+d);
    }
}

解析2:1，dp[i]为找零i所需的最小硬币数。2,初始化全部为i(最大值，找零1硬币的) 3，递推关系，dp[i]=min(dp[i],dp[i-num[j]]+1)

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int total = 1024;
        int cost = sc.nextInt();//总容量
        int change = total - cost;
        int[] dp = new int[change+1];
        for(int i = 1;i<=change;i++){
            dp[i] = i;
        }
        int[] num = {1,4,16,64};
        for(int i=1;i<=change;i++){
            for(int j=0;j<4;j++){
                if(i>=num[j]){//当找零要大于面额时
                     dp[i] = Math.min(dp[i],dp[i-num[j]]+1);
                } 
            }
        }
        System.out.print(dp[change]);
    }
}