题解 | #小红蹦跳蹦跳#

将left[i]定义为左脚到达第i阶，right[i]定义为右脚到达第i阶。可得

整理得

根据公式便可得出结果

#include<iostream>
#include<vector>
using namespace std;

const int MOD  = 1e9 + 7;
int main() {
    int n;
    cin >> n;
    vector<long long>left(n+5,0);
    vector<long long>right(n+5,0);
    left[1]=1;
    left[2]=0;
    right[1]=0;
    right[2]=1;
    for(int i=3;i<=n;i++){
        left[i]=(right[i-1]+left[i-2])%MOD;
        right[i]=(left[i-2]+right[i-2])%MOD;
    }
    long long res=(left[n]+right[n])%MOD;
    cout<<res<<endl;
    return 0;
}