首先一眼看出是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 閱讀(358)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態規劃