题解

思路

这个题有多种解法，我提供一下三种解法：

1. 使用正确程序打表或手算（后者是基本不可能的

2. dfs+一点剪枝

3. dp

代码

打表代码：

#include <iostream>
#include <vector>
#define int long long
using namespace std;
signed main(){
	int a[]={1,1,2,4,7,12,21,37,65,114,200,351,616,1081,1897,3329,5842,10252,17991,31572,55405,97229,170625,299426,525456,922111,1618192,2839729,4983377,8745217,15346786,0};
	int n;
	cin >> n;
	cout<<a[n]<<endl;
	return 0;
}

dfs+一点剪枝代码：

#include <iostream>
#include <vector>
using namespace std;
int res=0;
void dfs(const int n,vector<int> &a,int cnt){
	if (a.size()==n){
		if (cnt>=2 || cnt==0){
			++res;
		}
		return;
	}
	if (cnt==0 || cnt>=2){//一点小小的剪枝
		a.emplace_back(0);
		dfs(n,a,0);
		a.pop_back();//回溯 
	}
	a.emplace_back(1);
	dfs(n,a,cnt+1);
	a.pop_back();//回溯
}
int main(){
	int n;
	cin >> n;
	vector<int> a;
	dfs(n,a,0);
	cout<<res<<endl;
	return 0;
}

dp代码：

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