nyoj 01串 （DP）

描寫

ACM的zyc在研究01串，他知道某101串的長度，但他想知道不含有“11”子串的這類長度的01串共有多少個，他希望你能幫幫他。

注：01串的長度為2時,有3種：00，01，10。

輸入

第1行有1個整數n（0<n<=100）,表示有n組測試數據;
隨后有n行，每行有1個整數m(2<=m<=40)，表示01串的長度;

輸出

輸出不含有“11”子串的這類長度的01串共有多少個，占1行。

樣例輸入

2 2 3

樣例輸出

3 5

代碼：

#include<cstdio>
using namespace std;

int dp[1000];

int main()
{
    dp[0]=1;
    dp[1]=2;
    for(int i=2;i<=105;i++)
    {
        dp[i]=dp[i⑴]+dp[i⑵];
    }
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        printf("%d
",dp[n]);
    }
    return 0;
}

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈