题解|不连续1的子串

题目链接

核心思路：利用递归，把问题简化为n=1和n=2时的情况，n是子串长度，n=1时有2种可能，0或1，n=2时，可以在n=1的0后面拼接1或0，或在n=1的1后面拼接1。

#include<stdio.h>
using namespace std;
int f1(int N);
int f0(int N);
//末尾为1的串
int f1(int N) {
	if (N == 1)return 1;
	return f0(N - 1);
}
//末尾为0的串
int f0(int N) {
	if (N == 1)return 1;
	return f0(N - 1) + f1(N - 1);
}


int main() {
	int N;
	scanf("%d", &N);
	//有2种情况，若f（n）子串末尾是1，可由末尾为0的f(n-1)+1组成
	//若f（n）子串末尾是0，
	//可由末尾为0的f(n-1)+0组成或可由末尾为1的f(n-1)+0组成
	int cnt=f1(N)+f0(N);
	printf("%d\n", cnt);
	return 0;
}