題目大意：從1..n中選出若干個(gè)數(shù)字，要求滿足兩個(gè)條件：這些數(shù)字互不相臨；在不違背第一個(gè)條件的情況下，不能再這些數(shù)字組成的集合中加入新的數(shù)字。
簡(jiǎn)單分析即可得到思路：1或2必選其一；假設(shè)上一次選擇的是k，那么下一次要么選擇k+2，要么選擇k+3，否則就能夠加入新的數(shù)字；得到一個(gè)解的條件是(k==n||k+1==n)。如此一來(lái)，只要在遞歸中加入記憶化即可。
以下是我的代碼：
#include<stdio.h>
#include<string.h>
long n,d[87];
long dp(long now)
{
if(d[now]!=-1) return d[now];
d[now]=0;
if(now==n||now+1==n)
d[now]=1;
else
d[now]=dp(now+2)+dp(now+3);
return d[now];
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
while(scanf("%ld",&n)==1)
{
memset(d,-1,sizeof(d));
printf("%ld\n",(n>=2?dp(1)+dp(2):dp(1)));
}
return 0;
}