货币找零问题

题目

你要出去旅游，有N元的预算住酒店，有M家酒店供你挑选，这些酒店都有价格X。
需要你正好花完这N元住酒店（不能多，也不能少）最少能住几晚？返回最少住的天数，没有匹配的返回-1

• 比如你有1000元，所有酒店都是大于1000的，则返回-1
• 比如你有1000元，有1家1000元的，有1家300，有1家700。则最少能住1晚，最多住2晚（300+700）。返回1
• 比如你有1000元，有1家387元，有1家2元，有一家611，则返回3（3家各住1天）
• 比如你有1000元，有1家1元的，有一家2元的，有一家1001元的，则返回500（1元的1000天，2元的500天）

代码

import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        List<Integer> list = Arrays.stream(in.nextLine().split(" ")).map(Integer::parseInt).collect(Collectors.toList());
        int money = list.remove(list.size() - 1);
        int[] dp = new int[money + 1];
        for (int i = 1; i <= money; i++) {
            dp[i] = Integer.MAX_VALUE;
            if (i >= list.get(0) && dp[i - list.get(0)] != Integer.MAX_VALUE) {
                dp[i] = dp[i - list.get(0)] + 1;
            }
        }
        for (int i = 1; i <= money; i++) {
            for (int j = 0; j < list.size(); j++) {
                if (i >= list.get(j) && dp[i - list.get(j)] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - list.get(j)] + 1);
                }
            }
        }
        if (dp[money] != Integer.MAX_VALUE) {
            System.out.println(dp[money]);
        } else {
            System.out.println(-1);
        }
    }
}