poj 3181 Dollar Dayz

题意：给定一个数p，要求用K种币值分别为1,2,3...K的硬币组成p，问方案数，1,2,2和2,2,1算一种方案即与顺序无关，n <= 1000,k <= 100
// 用完全背包做了 这题也是母函数题目了

#include <iostream>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stdio.h>
#include <string.h>
using namespace std;
#define MOD 1000000007
#define maxn 1010
int dp[maxn][40];
void Add(int n,int m){

   int i;
   for(i=0;i<40;i++){
    dp[n][i]=dp[n][i]+dp[m][i];
    if(dp[n][i]>=10)
     dp[n][i]%=10,dp[n][i+1]++;
   }
}
int main()
{
    int N,K;
    while(scanf("%d %d",&N,&K)!=EOF){
        int i,j;
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(i=1;i<=K;i++)
           for(j=i;j<=N;j++)
              Add(j,j-i);//dp[j]+=dp[j-i]; 想都没想 就这么写 这么提交了 高精度啊 不WA 才怪
     // printf("%d
",dp[N]);
       for(i=39;i>=0;i--) if(dp[N][i]) break;
       for(;i>=0;i--)printf("%d",dp[N][i]);
       printf("
");
    }
    return 0;
}