暴力

#include<iostream>
using namespace std;
int n,ans;
bool check(int x){
    for(int i=0;i<n;i++){
        int j=i+1;
        if(j<n){
            if((x>>i&1)+(x>>j&1)==2){
                return 0;
            }
        }
    }
    return 1;
}
int main(){
    cin>>n;
    for(int i=0;i<(1<<n);i++) if(check(i)) ans++;
    cout<<ans<<endl;
    return 0;
}

DFS

#include<iostream>
using namespace std;
int n,ans;
string s="0";
void dfs(int id,string s){
    if(id>n){
        ans++;
        return ;
    }
    if(s[id-1]=='0') dfs(id+1,s+"1");
    dfs(id+1,s+"0");
}
int main(){
    cin>>n;
    dfs(1,s);
    cout<<ans<<endl;
    return 0;
}

DP

#include<iostream>
using namespace std;
const int N=25;
int n,dp[N][2];
//dp[i][0]:以0结尾,长度为i的所有不连续1的串的个数的集合
//dp[i][1]:以1结尾,长度为i的所有不连续1的串的个数的集合
//性质:cnt
//状态计算:
//dp[i][0]=dp[i-1][1]+dp[i-1][0];
//dp[i][1]=dp[i-1][0];
int main(){
    cin>>n;
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        dp[i][0]=dp[i-1][1]+dp[i-1][0];
        dp[i][1]=dp[i-1][0];
    }
    cout<<dp[n][0]+dp[n][1]<<endl;
    return 0;
}