原题地址
这道题卡了我很长时间，主要是没明白规律。
这里借用一下别人的讲法：
我们用 f[n] 表示有n个座位，且至少坐一个人的坐法种类数。
f[n]有两种情况：
1.最后一个位置不坐人，则等价于f[n-1]
2.最后一个位置坐人，则n-1，n-2的位置就不能坐人了，这样等价于f[n-3],但最后一个位置已经坐人了所以前n-3个位置可以不做人，因此总的f[n-3]+1;

原文：https://blog.csdn.net/qq_32426313/article/details/54346610

#include<iostream>
#include<vector>
#include<bits/stdc++.h>
//#include<math.h>
using namespace std;

long long  gcd(int n){
    long long  f[999];
    f[1]=1;
    f[2]=2;
    for(int i=3;i<=n;i++)
        f[i] = f[i-3]+f[i-1]+1;
    return f[n];
}

int main( )
{
    int n,m ;
   while(cin >>n){

     cout<<gcd(n)<<endl;
   }

    return 0;

}