Description
Input
Output
Sample Input
| input | output |
|---|---|
212 |
995645335 |
大意：n块砖头，让你排成一个楼梯，满足列数大于2，并且后面列的高度大于前面列的高度所有可能的情况种类
初始化：dp[i][i] = 1 表示一共有i块砖头，在当前（也就是最后一列）把所有的砖块都放上只有一种
状态转移方程 dp[i][j] += dp[i-j][0..j-1] 一共i个砖块最后一列为j个 状态是由前面一个状态转移过来的 即少了最后一列砖块现在变成i-j块的所有的情况，这个k必须小于j，最后答案就是dp[n][0..n-1] 除了一共有n块，最后一列全是n的情况，开long long orz
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long dp[550][550];
int main()
{
int n;
while(~scanf("%d",&n)){
memset(dp,0,sizeof(dp));
for(int i = 1; i <= n ;i++)
dp[i][i] = 1;
//用了i块砖头，当前有i块砖头
for(int i = 1; i <= n ;i++){
for(int j = 1; j < i ;j++){
for(int k = 0; k < j ;k++){
dp[i][j] += dp[i-j][k];
}
}
}
long long ans = 0;
for(int i = 0 ; i < n;i++)
ans += 1ll*dp[n][i];
printf("%lld\n",ans);
}
return 0;
}
原文：http://www.cnblogs.com/zero-begin/p/4488947.html