算法1
(暴力枚举) dp算法
状态转移
a[i]=a[i-1]+a[i-2];
时间复杂度 O(n)
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
//dp
const int N=30;
int a[N];
int n;
int main()
{
cin>>n;
a[0]=a[1]=1;
for(int i=2;i<=n;i++)a[i]=a[i-1]+a[i-2];
cout<<a[n]<<endl;
}
算法2
dfs
blablabla
时间复杂度
o(状态数)
参考文献
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
/*
dfs 转换成为一个状态树
*/
int n,ans;
void dfs(int u)
{
//边界条件
if(u<=1)
{
ans++; //只用一个1的情况
return ;
}
dfs(u-1);
dfs(u-2);
return ;
//
}
int main()
{
cin>>n;
dfs(n);//根结点的值
cout<<ans<<endl;
}