题解 | 硬币凑钱

#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")