PKU 3181 Dollar Dayz

http://poj.org/problem?id=3181
nドルのものを1〜Kドルまでの貨幣で支払うとき、何通りの支払い方があるかを答えろというような問題。

多倍長+DP。
遅い多倍長でTLEもらいました。

char* add(char* a,char* b,char* out){
  int as=strlen(a),bs=strlen(b);
  int c=0;
  int sz=0;
  rep(i,max(as,bs)){
    int t=c;
    if(i<as)t+=a[i]-'0';
    if(i<bs)t+=b[i]-'0';
    c=t/10;
    t%=10;
    out[sz++]=t+'0';
  }
  if(c)out[sz++]=c+'0';
  out[sz]=0;
  return out;
}

char dp[1100][110][40];
bool vis[1100][110];
char zero[]="0";
char one[]="1";

char* rec(int n,int k){
  if(n<0 || k<1)return zero;
  if(n==0)return one;
  if(vis[n][k])return dp[n][k];
  vis[n][k]=true;
  return
    add(rec(n,k-1),rec(n-k,k),dp[n][k]);
}

main(){
  int n,k;
  cin>>n>>k;
  string ans(rec(n,k));
  reverse(ALL(ans));
  cout<<ans<<endl;
}