HDOJ 1028(整数划分)

/*
大概思路是开2个数组，c1[ ]保存当前得到的多项式各项系数，c2[ ]保存每次计算时的临时结果，
当每次计算完毕后，把它赋给c1，然后c2清零。
计算的时候，开3层for循环。最外层，记录它正在与第几个多项式相乘。
第二层，表示c1中的每一项，第三层表示后面被乘多项式中的每一项。
*/
#include <stdio.h>
#include <string.h>
const int MAX=120;
int main()
{
    int n,c1[MAX+5],c2[MAX+5];
    while(~scanf("%d",&n))
    {
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));
        c1[0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=n;j++)
            {
                for(int k=0;j+k*i<=n;k++)
                {
                    c2[j+k*i] += c1[j];
                }
            }
            memcpy(c1,c2,sizeof(c2));
            memset(c2,0,sizeof(c2));
        }
        printf("%d\n",c1[n]);
    }
    return 0;
}









//非常不理解 
#include<stdio.h>
#define N 130
int dp[N][N];
int main()
{
	int i,j,T;
    for(i=0;i<N;i++)
    {
        dp[0][i]=1;dp[1][i]=1;dp[i][1]=1;
    }
    for(i=2;i<N;i++)
        for(j=2;j<N;j++)
            if(j<=i)
                dp[i][j]=dp[i][j-1]+dp[i-j][j];
            else
                dp[i][j]=dp[i][j-1];
    while(scanf("%d",&T))
        printf("%d\n",dp[T][T]);
    return 0;
}