牛客网真题-62-找零钱

最值问题一般两个思路，贪心和dp
本题显然也可以通过dp求解，与斐波那契数列的思路一致：
构建数组int[1024],表示最少硬币数
dp[n]=min(dp[n-64]，dp[n-16]，dp[n-4]，dp[n-1])，注意小于64取后三项，小于16取后两项
如果是多个测试用例一起，这样会很快，因为只要查表就好了。
说了半天我是用贪心求解的哟

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int input = 1024 - scanner.nextInt();
        int cnt = 0;
        int[] money = new int[]{64, 16, 4, 1};
        for(int i = 0; i < money.length; i++){
            cnt += input / money[i];
            input = input % money[i];
        }
        System.out.println(cnt);
    }
}