HDU1028 （DP）

题意：整数划分问题是将一个正整数n拆成一组数连加并等于n的形式，且这组数中的最大加数不大于n。

#include<stdio.h>
const int maxn = 124;
int dp[ maxn ][ maxn ];
int main(){
    for( int i=0;i<maxn;i++ ){
        //dp[ 0 ][ i ]=dp[ i ][ 0 ]=0;
        dp[ 1 ][ i ]=dp[ i ][ 1 ]=1;
    }
    for( int i=2;i<=120;i++ ){
        for( int j=2;j<=120;j++ ){
            if( i==j ) dp[ i ][ j ]=dp[ i ][ j-1 ]+1;
            else if( i<j ) dp[ i ][ j ]=dp[ i ][ i ];
            else dp[ i ][ j ]=dp[ i ][ j-1 ]+dp[ i-j ][ j ];
        }
    }
    int n;
    while( scanf("%d",&n)!=EOF ){
        printf("%d\n",dp[ n ][ n ]);
    }
    return 0;
}