2846. 统计字符串个数

动态规划。
思路：f(n)=f(n-1)+(f(n-1)-f(n-2)+f(n-3))。解释：长度为n的不含101的字串有2种可能：第一，长度为n-1的不含101的字串结尾+0；第二：长度为n-1的不含101的字串结尾+1。但第二种情况应除去结尾是101的字串。具体操作为减去结尾为01的字串再加上结尾为001的字串。

#include <iostream>
using namespace std;
int main()
{
    int m, n[21]={0};
    n[1]=2;
    n[2]=4;
    n[3]=7;
    for(int i=4; i<21; i++) n[i]=2*n[i-1]-n[i-2]+n[i-3];
    cin>>m;
    while(m+1){cout<<n[m]<<endl;cin>>m;}
    return 0;
}

设 $a[n]$ 是以 $0$ 结尾的不含 $101$ 的长为 $n$ 的字符串的个数，$b[n]$ 是以 $1$ 结尾的不含 $101$ 的长为 $n$ 的字符串的个数。

Base Case:

$$
a[0] = b[0] = 0, \
a[1] = b[1] = 1.
$$
对 $a$ 而言，有 $a[n] = a[n-1]+b[n-1]$；即：长为 $n - 1$ 的不含 $101$ 的字符串后再加一个 $0$。

对 $b$ 而言，有 $b[n] = (b[n-1]) + (a[n-1] - b[n-2])$；即：长为 $n - 1$ 的不含 $101$ 的也不以 $10$ 结尾的字符串后再加一个 $1$。

由此可以得到公式：
$$
a[n] = a[n-1]+b[n-1];\
b[n] = a[n] - b[n-2];
$$
代码：

int main() {
    uint32_t a[21], b[21];
    a[0] = b[0] = 0, a[1] = b[1] = 1;
    for (uint32_t i = 2; i <= 20; ++i)
        a[i] = a[i - 1] + b[i - 1],
        b[i] = a[i] - b[i - 2];
    for (int n; std::cin >> n, n != -1;)
        printf("%u\n", a[n] + b[n]);
}

//广度遍历+剪枝
//性能不算太好，但是容易想到

include

include

include

include

using namespace std;

int main()
{
int n;
string str;
while (cin >> n && n != -1) {
int count = 0;
queueMyQueue;
MyQueue.push(“”);
while (!MyQueue.empty()) {
str = MyQueue.front();
MyQueue.pop();
if (str.size() == n) {
if (str.find(“101”) == string::npos) {
count++;
}
}
else {
if (str.find(“101”) == string::npos) {//剪枝：已有“101”的直接排除
MyQueue.push(str + “0”);
MyQueue.push(str + “1”);
}
}
}
printf(“%d\n”, count);
}
return 0;
}

看了大佬们的解析，我来说一个复杂一点但很好理解的方法

用$t00[n]$ , $t01[n]$, $t10[n]$, $t11[n]$ 四个数列表示以00, 01, 10, 11结尾的不含 101 的字符串个数

递推公式比较好理解

比如 $t00[n] = t00[n-1] + t10[n-1]$ 表示以00结尾的长度为n的字符串要么是00结尾长n-1的字符串尾部加上0, 或是10结尾长n-1的字符串尾部加上0，且这两种方式并不会产生含”101”的字符串, 因为$t00[n-1]$和$t10[n-1]$本身不包含”101”, 而在尾部添加0也不会产生”101”

当然, 以01结尾的字符串不能由10结尾的字符串添加1得到, 否则产生了”101”

类似的, $t01[n] = t00[n-1]$
$t10[n] = t01[n-1] + t11[n-1]$
$t11[n] = t01[n-1] + t11[n-1]$
都成立, 这些是递推公式

代码如下:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t00[21], t01[21], t10[21], t11[21];
    t00[2] = 1, t01[2] = 1, t10[2] = 1, t11[2] = 1;
    for(int i = 3; i <= 20; ++i)
    {
        t00[i] = t00[i-1] + t10[i-1];
        t01[i] = t00[i-1];
        t10[i] = t01[i-1] + t11[i-1];
        t11[i] = t01[i-1] + t11[i-1];
    }
    int n;
    while(1)
    {
        cin >> n;
        if(n == -1) break;
        if(n == 1) 
        {
            cout << 2 << endl;
            continue;
        }
        cout << t00[n] + t01[n] + t10[n] + t11[n] << endl;
     }
    return 0;
}

感谢讲解