非常简单

时间复杂度：O(n)，因为我们只需遍历一次从 0 到 n。
空间复杂度：O(n)，用于存储跳法的数量。

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

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

    // 创建一个大小为 n+1 的数组来保存不同的跳法
    vector<int> dp(n + 1, 0);

    // 基本情况
    dp[0] = 1; // 到达第 0 阶的方法数
    if (n >= 1) dp[1] = 1; // 到达第 1 阶的方法数
    if (n >= 2) dp[2] = 1; // 到达第 2 阶的方法数
    if (n >= 3) dp[3] = 2; // 到达第 3 阶的方法数

    // 动态规划计算
    for (int i = 4; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 3]; // 递推关系
    }

    // 输出结果
    cout << dp[n] << endl;
    return 0;
}

输入处理：读取台阶数 n。
数组初始化：使用一个大小为 n + 1 的动态规划数组 dp 来保存到达每个台阶的不同跳法。
基本情况设定：根据我们之前讨论的基本情况来初始化数组。
动态规划计算：从第 4 阶开始，根据递推关系计算到达每个台阶的方法数。
输出结果：最后输出 dp[n]，即到达第 n 阶的方法数。