# 2846. 统计字符串个数

#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;
}


Base Case:

$$a[0] = b[0] = 0, \ a[1] = b[1] = 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

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;
}

$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;
}