硬币凑钱

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.close();

        System.out.println(minCoins(n));
    }

    /**
     * 计算凑成n元所需的最少硬币数量
     * 可用硬币面值为7元、5元、1元，数量无限
     */
    private static int minCoins(int n) {
        // dp[i]表示凑成i元所需的最少硬币数量
        int[] dp = new int[n + 1];

        // 初始化：0元需要0个硬币
        dp[0] = 0;

        // 其他金额初始化为一个较大值（最多不会超过n个1元硬币）
        for (int i = 1; i <= n; i++) {
            dp[i] = n + 1; // 赋一个比可能的最大值大的值
        }

        // 动态规划计算
        for (int i = 1; i <= n; i++) {
            // 考虑使用1元硬币的情况
            if (i >= 1) {
                dp[i] = Math.min(dp[i], dp[i - 1] + 1);
            }

            // 考虑使用5元硬币的情况
            if (i >= 5) {
                dp[i] = Math.min(dp[i], dp[i - 5] + 1);
            }

            // 考虑使用7元硬币的情况
            if (i >= 7) {
                dp[i] = Math.min(dp[i], dp[i - 7] + 1);
            }
        }

        return dp[n];
    }
}