不知道我在任务中哪里错了

Question

对于某个n，我们必须确定只有'0'和'1'组成的不同字符串的数量，其中没有两个相邻的'1'。(字符串的大小是n)对不起，我的英语不好。这是我的尝试:

long Num(int n){
    if(n==0)
        return 0;
    else if(n==1)
        return 2;
    else if(n==2)
        return 3;
    else if(n==3)
        return 5;
    else
        return 2*Num(n-2) + Num(n-3);
};

Answer 1

问题:

求长度为n且不连续为1的可能二进制字符串的个数

输入/输出:

输入:N = 2输出:3//三个字符串分别是00,01,10

输入:N = 3输出:5//5个字符串分别是000,001,010,100,101

方法:

设a[i]为长度为i且不包含任何两个连续的1且以0结尾的二进制字符串的个数。同样，设b[i]为以1结尾的字符串的个数。我们可以在以0结尾的字符串后面加上0或1，但是我们只能在以1结尾的字符串后面加上0。这产生了递归关系:

a[i] = a[i - 1] + b[i - 1]
b[i] = a[i - 1] 

上述递归式的基本情况为a[1] = b[1] = 1。长度为i的字符串的总数就是a[i] + b[i]。当使用数组i (length of string)时，对于数组的零位，将减少1。

解决方案:

int countStrings(int n)
{
    int a[] = new int [n];
    int b[] = new int [n];
    a[0] = b[0] = 1;
    for (int i = 1; i < n; i++)
    {
        a[i] = a[i-1] + b[i-1];
        b[i] = a[i-1];
    }
    return a[n-1] + b[n-1];
}

详细信息请参见http://www.geeksforgeeks.org/count-number-binary-strings-without-consecutive-1s/