这题和Fibonacci数列比较相似，本质上是一个简单的动态规划。 递推公式为：dp[i] = dp[i-1] +dp[i-2] 注意dp数组的初始化，dp[1]=1,dp[2]=2。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL dp[100];

int main(){
// dp[n] = dp[n-1] + dp[n-2]
// dp[0] = ? dp[1] = 1 dp[2] = 2
int n;
cin>>n;
dp[1]=1;dp[2]=2;
for(int i=3;i<=n;i++){
dp[i] = dp[i-1]+dp[i-2];
}
cout<<dp[n];
return 0;

}