记忆化搜索

AC:3 WA:5 

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N];
int n;
int dfs(int u,int last)
{
    if(u==0)
    {
        return 1;
    }
    if(f[u]!=-1) return f[u];
    f[u]=0;
    if(u>=10&&u>=last) f[u]+=dfs(u-10,10);
    if(u>=20&&u>=last) f[u]+=dfs(u-20,20);
    if(u>=50&&u>=last) f[u]+=dfs(u-50,50);
    if(u>=100&&u>=last) f[u]+=dfs(u-100,100);
    return f[u];
}
int main()
{
    memset(f,-1,sizeof f);
    cin>>n;
    cout<<dfs(n,10);
    return 0;
}

动态规划

AC:8 WA:0

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[]={0,10,20,50,100};
int f[N];
int main()
{
   int n;
   cin>>n;
   f[0]=1;
   for(int i=1;i<=4;i++)
   {
      for(int j=v[i];j<=n;j++)
      {
         f[j]=f[j]+f[j-v[i]];
      }
   }
   cout<<f[n];
   return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[]={0,10,20,50,100};
int f[N];
int main()
{
   int n;
   cin>>n;
   f[0]=1;
   for(int i=1;i<=4;i++)
   {
      for(int j=v[i];j<=n;j++)
      {
         f[j]=f[j]+f[j-v[i]];
      }
   }
   cout<<f[n];
   return 0;
}