题解 | 硬币凑钱

import java.util.Scanner;

/**
 * @author supermejane
 * @date 2025/10/7
 * @description BGN64 硬币凑钱
 */
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long[] dp = new long[n + 1];
        for (int i = 1; i <= n; i++) {
		  	//状态转移
            dp[i] = Math.min(Math.min(getVal(dp, i - 5), getVal(dp, i - 7)), getVal(dp, i - 1)) + 1;
        }
        System.out.println(dp[n]);
    }
	//处理边界
    public static long getVal(long[] dp, int i) {
        if (i > 0) return dp[i];
        else if (i == 0) return 0;
        else return Integer.MAX_VALUE;
    }
}