牛客网真题-62-找零钱
找零
http://www.nowcoder.com/questionTerminal/944e5ca0ea88471fbfa73061ebe95728
最值问题一般两个思路，贪心和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);
}
}
左边刷题右边 chat 效果很好