不太会的dfs算法 QAQ

#include<iostream>

using namespace  std;
bool light[35];
long long ans;

void  dfs(int n)
{
	if (n == 31)//边界判断
	{
		ans++;
		return;
	}
	if (light[n - 1]) dfs(n + 1);
	//前灯亮则此灯不亮，进入下一层搜索
	else {//前灯不亮
		light[n] = true;//标记
		dfs(n + 1);//此灯亮
		light[n] = false;//重新标记
		dfs(n + 1);//此灯不亮
	}

}
int main(void)
{
	int sum = 30;
	dfs(1);
	cout << ans;

	return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//通过列出前5项，找到规律，这是一个斐波那契数列
//数据范围小，不需要记搜，直接递推就完了
ll fib(int x){
    if(x==1)return 2;
    if(x==2)return 3;
    return fib(x-1)+fib(x-2);
}
int main(){
  cout<<fib(30);
  return 0;
}

动态规划题

#include <bits/stdc++.h>
using namespace std;
long long dp[2][38];
int main(){
	dp[0][1]=1,dp[1][1]=1;
	for(int i=2;i<=30;i++){
		dp[0][i]=dp[0][i-1]+dp[1][i-1];
		dp[1][i]=dp[0][i-1];
	}
	cout<<dp[0][30]+dp[1][30];
	return 0;
}