ACM的zyc在研究01串，他知道某一01串的长度，但他想知道不含有“11”子串的这种长度的01串共有多少个，他希望你能帮帮他。
注：01串的长度为2时,有3种：00，01，10。
输入 第一行有一个整数n（0<n<=100）,表示有n组测试数据; 随后有n行，每行有一个整数m(2<=m<=40)，表示01串的长度; 输出 输出不含有“11”子串的这种长度的01串共有多少个，占一行。 样例输入 2 2 3 样例输出 3 5思路：
1.设长度为k的字符串中不含‘11’子串的字符串个数为dp[k]
(1).当第k个字符为0时，不含“11”的子串个数为dp[k-1]
(2).当第k个字符为1时，k-1位必定为0，所以不含“11”的子串为dp[k-2]
2.找规律，就是斐波那契数列
代码：
#include<stdio.h> int main() { int dp[50];// dp[2]=3; dp[3]=5; for(int i=4;i<=42;i++) { dp[i]=dp[i-1]+dp[i-2]; } int n; int a; scanf("%d",&n); while(n--) { scanf("%d",&a); printf("%d\n",dp[a]); } }
