题目描述

有1~n面值的硬币凑出数额为m的值

DP

一开始的想法是DP，因为DP入门题就有一题凑硬币，然而TLE了，只过了6个样例；

试图优化ing，观察发现只需要对m%n进行DP后加上m/n即可，因为在1~n的部分的结果肯定是1，然而还是只比DP多过了一个样例

年轻人不要听风就是雨，以为凑的硬币多了，上来就想DP，naive！

TLE的DP代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10;

int dp[N];

int main()
{
    int n,m;
    cin>>n>>m;
    int cnt=m/n;
    m%=n;
    memset( dp, 0x3f, sizeof dp);
    dp[0]=0;
    for(int i=1;i<=m;i++)
    {
        for(int coin=1;coin<=n;coin++)
        {
            if(i-coin<0) continue;
            dp[i]=min(dp[i],dp[i-coin]+1);
        }
    }
    cout<<dp[m]+cnt<<endl;
    return 0;
}

AC思路

从上面的思路走下来，发现m%n的部分也不需要dp,由于m%n是小于n的，所以当（m%n==0）答案为m/n，否则为m/n+1
原来是这么简单的入门题？!

#include<iostream>
using namespace std;

int main()
{
    int n,m;
    cin>>n>>m;
    if(!(m%n)) cout<<m/n<<endl;
    else cout<<m/n+1<<endl;
    return 0;
}