【题意】：给出一个长度为n的序列，要求用数字0或者1填补，要求每两个1都不能相邻，问有多少种填法？


【题解】：定义dp[i][0],表示已经填了 i 个数字，且最后的数字为0.
              定义dp[i][1],表示已经填了 i 个数字，且最后的数字为1.
              转移方程：
                          dp[i][0] = dp[i-1][0] + dp[i-1][1];
                          dp[i][1] = dp[i-1][0];
              显然最后答案 ans = dp[n][0] + dp[n][1];

【代码】：

 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 using namespace std;
 5 #define maxn 50
 6 int dp[maxn][2];
 7 int main() {
 8     int T, n;
 9     dp[1][0] = dp[1][1] = 1;
10     for(int i = 2; i < maxn; i++) {
11         dp[i][0] = dp[i-1][0] + dp[i-1][1];
12         dp[i][1] = dp[i-1][0];
13     }
14     scanf("%d", &T);
15     for(int t = 1; t <= T; t++) {
16         scanf("%d", &n);
17         int ans = dp[n][0] + dp[n][1];
18         printf("Scenario #%d:\n", t);
19         printf("%d\n\n", ans);
20     }
21     return 0;
22 }