c++ - 没有连续 1 的位串，使用自顶向下 DP

Question

计算所有没有两个连续 1 的不同二进制字符串

我试图将自下而上的动态编程方法（在链接中提到）转换为递归关系，但无法获得正确的输出。

#include<iostream>
#define n 4
using namespace std;


int bitstring(int N, int b = 0)
{
    static int s = 0;
    //termination condition
    if (N == 1)
        return 1;
    if(b == 1)
    {
        s += bitstring(N - 1, 0);
    }
    if (b == 0)
    {
        s = bitstring(N - 1, 0) + bitstring(N - 1, 1);
    }
    return s;
}

int main()
{
    cout << bitstring(n) << endl;
    return 0;
}

对于 N = 3，输出为5

N=3 的插图

                f(3,0)        f(3,1)
                /     \          |
            f(2,0)  f(2,1)     f(2,0)
            /   \      |       /     \
        f(1,0) f(1,1) f(1,1)  f(1,0)  f(1,1)
          |      |       |      |        |
          1      1       1      1        1

标签： c++dynamic-programmingbitstring

Answer 1

至少对于N==1您有两个序列 [0] 和 [1] 的情况。可能最好从极端案例开始^_^ 对于案例b==1和b==0您使用不同的操作s，应该是这样吗？