题解 | 硬币凑钱

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

class Pair {
    public int num;
    public int step;
    public Pair(int num, int step) {
        this.num = num;
        this.step = step;
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        // while (in.hasNextInt()) { // 注意 while 处理多个 case
        //     int a = in.nextInt();
        //     int b = in.nextInt();
        //     System.out.println(a + b);
        // }
        // 使用bfs 11.07
        int num = in.nextInt();
        System.out.println(getMin(num));


    }

    public static int getMin(int num) {
        boolean[] isVisist = new boolean[num + 1];
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(num, 0));
        isVisist[num] = true;
        int[] allArr = new int[] {7, 5, 1};

        while (!queue.isEmpty()) {
            Pair current = queue.poll();
            int numCurr = current.num;
            int step = current.step;

            for (int i = 0; i < allArr.length; i++) {
                int jian = numCurr - allArr[i];
                if (jian == 0) {
                    return step+1;

                }
                int jiaStp =0;
                if(jian>0 && !isVisist[jian]){
                    jiaStp = step+1;
                    queue.add(new Pair(jian,step+1));
                    isVisist[jian] = true;;
                }
                
            }


        }
        return 0;
    }


}