【題意】：給出一個長度為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 }