hdu 1028 Ignatius and the Princess III

这道题不水，是一道非常经典的dp题，有兴趣的同学也可以考虑用母函数来做，非常方便，但要注意有模板哦。

#include<stdio.h> #include<string.h> #define maxn 130 int dp[maxn][maxn];//第一个数表示要分解的数，第二个数表示分解结果中最大数的值 int calc(int x,int y) { if(dp[x][y]!=-1) return dp[x][y]; if(x==1||y==1) return dp[x][y]=1; if(x==y) return dp[x][y]=calc(x,y-1)+1;//如果分解的最大数就是本身，那么就等于分解的最大数-1的结果数+1 if(x<y) return dp[x][y]=calc(x,x); if(x>y) return dp[x][y]=calc(x,y-1)+calc(x-y,y);//要么实际分解出来的最大数确实是y，要么就是实际分解出来的最大数是y-1 } int main() { int N; while(scanf("%d",&N)==1) { memset(dp,-1,sizeof(dp)); int key=calc(N,N); printf("%d\n",key); } return 0; }