题目描述

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

输入描述

一行，包含一个数N

输出描述

一行，包含一个数，表示最少收到的硬币数

示例1输入：

200

示例1输出:

17

解题思路

1. 这道题属于典型的入门级动态规范，回顾一下动态规范三个条件，最优子结构，转移方程以及边界条件
2. 现在假设我们要求的结果是F(n)，其中n为我们要找零的钱，根据钞票种类，只有1/4/16/64这四种，那么如果要F(n)最小，那么最优子结构就应该是F(n)=min{F(n-1, F(n-4), F(n-16), F(n-64)}+1,以此递推到边界为1或者2或者3或者4的时候，即可终止得到边界条件
3. 然后我们将递推反过来叠加式求解，可以声明一个数组为N+1（数组下标从0开始，将下标和金额对应），写入初始条件，依次往上叠加求解，就可以得到结果

解题代码

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int expense = sc.nextInt();
        int re = 1024-expense;
        if (re==0) {
            System.out.println(0);
            return;
        }
        if (re==1) {
            System.out.println(1);
            return;
        }
        if (re==2) {
            System.out.println(2);
            return;
        }
        if (re==3) {
            System.out.println(3);
            return;
        }
        if (re==4) {
            System.out.println(1);
            return;
        }
        int[] result = new int[re+1];
        result[0]=0;
        result[1]=1;
        result[2]=2;
        result[3]=3;
        result[4]=1;
        for(int i=5; i<=re; i++) {
            if(i=16 || i=64) result[i] = 1;
            else if(i>16 && i<64) result[i] = Math.min(Math.min(result[i-1],result[i-4]),result[i-16])+1;
            else if(i>64) result[i]=Math.min(Math.min(result[i-1], result[i-4]), Math.min(result[i-16], result[i-16]))+1;
            else result[i]=Math.min(result[i-1], result[i-4]);
        }
        system.out.println(result[re]);
    }
}