首先一眼看出是DP。先不考虑“每个楼梯至少有2格”这个条件，因为加上这个条件之后DP就不满足无后效性了；另外只有1格的情况只有一种，算出全部的之后再减去即可。
这样，d[i][j]表示当前楼梯共用了i块砖，且最后一格共j个砖的方案数，则：
d[0][0]=1
d[i][j]=sum{ d[i-j][k],0<=k<j }
以下是我的代码：
#include<iostream>
#include<string.h>
#define maxn 507
using namespace std;
long long n,ans,d[maxn][maxn];
int main()
{
cin>>n;
memset(d,0,sizeof(d));
d[0][0]=1;
for(long i=1;i<=n;i++)
for(long j=1;j<=i;j++)
for(long k=0;k<=j-1;k++)
d[i][j]+=d[i-j][k];
ans=0;
for(long i=1;i<=n;i++)
ans+=d[n][i];
ans-=1;
cout<<ans<<endl;
return 0;
}
posted on 2010-09-11 17:45
lee1r 阅读(330)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：动态规划