给一组数字，按a..z为1..26排求出能组成多少种不同的字母链。
简单的DP，边界条件f[0]=1,f[1]=1,f[n]=f[n-1](如果第n个字符即s[n-1]!=48),f[n]+=f[n-2](如果第n和第n-1个字符能组成小于26的数字)
#include<cstdio> #include<cstring> char s[5005]; int i,j,l; long long f[5005]; int main(){ while(scanf("%s",s)&&s[0]!=48){ l=strlen(s); memset(f,0,sizeof(f)); f[1]=1;f[0]=1; for (i=2;i<=l;i++){ if (s[i-1]!=48)f[i]=f[i-1]; if (s[i-2]==49)f[i]+=f[i-2]; else if (s[i-2]==50&&s[i-1]<55)f[i]+=f[i-2]; } printf("%lld\n",f[l]); } }
原文：http://www.cnblogs.com/moris/p/4316740.html