题目描述
不连续1的字串
二进制枚举更简单,且答案更多一点。这里提供dfs的思路:从第一位到第n位,每一位都可以取到0或1,但是不能出现连续的1。写一个dfs函数,然后递归即可
样例
blablabla
算法1
C++ 代码
#include<iostream>
using namespace std;
const int N = 30;
int n,ans;
int path[N];
void dfs(int x){
if(x > n){
ans++;
return;
}
for(int i = 0;i <= 1;i++){
path[x] = i;
if((path[x] == 1 && path[x-1] == 1)) return;
dfs(x+1);
}
}
int main(){
cin>>n;
dfs(1);
cout<<ans<<endl;
return 0;
}