硬币凑钱

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];
    }
}

#include <iostream>
using namespace std;
const int N = 1e6+10;
int main() {
    int n;
    int dp[N]={0};
    cin>>n;
   for(int i=1;i<=n;i++){
    if(i<5)dp[i]=dp[i-1]+1;
    else if(i>=5&&i<7)dp[i]=min(dp[i-1]+1,dp[i-5]+1);
    else if(i>=7)dp[i]=min(dp[i-5]+1,dp[i-7]+1);
   }
   cout<<dp[n];
}

#include <iostream>
using namespace std;
#include<vector>
#include<algorithm>
#define N 1e6
vector<int>dp(N,N);
vector<int>coins{1,5,7};
int coinnum(int n){//n元需要的硬币数
    //最小子问题 
    if(n==0){
    dp[0]=0;
    return dp[n];
    }
    if(dp[n]!=N){//已经缓存过的值
        return dp[n];
    }
    //状态转移方程   
    //思路 先取一枚硬币 问题就变成了找另外部分的子问题
    //例如 取一枚1元硬币 问题就变成了找n-1元的子问题   1+f(n-1)
    //     取一枚5元硬币 问题就变成了找n-5元的子问题   1+f(n-5)
    //     取一枚7元硬币 问题就变成了找n-7元的子问题   1+f(n-7)
    //  1+f(n-1)   1+f(n-5)   1+f(n-7)  比较这三个值 找出最小值
    int mincoin=N;
    for(int coin:coins){
        if(n>=coin){
            mincoin=min(mincoin,coinnum(n-coin)+1);
        }
    }
    dp[n]=mincoin;
    return dp[n];
}

signed main() {
   int n;
   cin>>n;
   cout<<coinnum(n);
}
// 64 位输出请用 printf("%lld")