题解 | 小红蹦跳蹦跳

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

const int MOD = 1e9+7;

int main() {
    int n;cin>>n;

    vector<long long> dp_odd(n+1,0);
    vector<long long> dp_eve(n+1,0);

    //初始条件
    dp_eve[0] = 1;           //0级台阶，偶数步到达
    if(n>=1) dp_odd[1] = 1;  //左脚直接跳1级

    //动态规划
    for(int i=2;i<=n;i++)
    {
        dp_odd[i] = (dp_eve[i-1]+dp_odd[i-2]) % MOD;
        dp_eve[i] = (dp_eve[i-2]+dp_odd[i-2]) % MOD;
    }

    // 总方案数：奇数步或偶数步到达n级
    long long result = (dp_odd[n] + dp_eve[n]) % MOD;
    cout << result << endl;

    return 0;

}
// 64 位输出请用 printf("%lld")