01串（dp）

01串

时间限制：1000 ms  |  内存限制：65535 KB

难度：2

 

描述

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
题解：简单dp；dp[i][j]代表以j结尾的串；
代码：

import java.util.Scanner;


public class nyoj01串 {
    public static void main(String[] argvs){
        int n, m;
        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();
        while(n-- > 0){
            m = cin.nextInt();
            //System.out.println("m =" + m);
            int dp[][] = new int[m + 1][2];
            dp[1][0] = 1;dp[1][1] = 1;
            for(int i = 2; i <= m; i++){
                dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
                dp[i][1] = dp[i - 1][0];
            }
            System.out.println(dp[m][0] + dp[m][1]);
        }
    }
}