ural 1017. Staircases(dp)

http://acm.timus.ru/problem.aspx?space=1&num=1017

题意：有n块砖，要求按照严格递增的个数摆放成楼梯，求楼梯的摆放种类数。

思路：状态转移方程：dp[i][j]=sum(dp[i-j][k]), 0 < k < j; i 表示砖的总数，j表示最高的那层的个数。

#include <stdio.h>
#include <string.h>
#define LL long long
const int N=502;
LL dp[N][N];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(dp,0,sizeof(dp));
        for (int i = 1; i <= n; i++)
            dp[i][i] = 1;
        dp[3][2] = 1;
        dp[4][3] = 1;
        for (int i = 5; i <= n; i++)
        {
            for (int j = 1; j < i; j++)
            {
                for (int k = 1; k < j; k++)
                    dp[i][j]+=dp[i-j][k];
            }
        }
        LL ans = 0;
        for (int i = 1; i < n; i++)
            ans+=dp[n][i];
        printf("%lld
",ans);
    }
    return 0;
}