c++跳楼梯问题递归超时

c++跳楼梯问题如下

然后我用一个函数，以 j 计数，用递归解决，代码如下

#include 
using namespace std;
void cs(int n,int &j)
{
    if(n==2||n==3)
    {
        j++;
        j=j%1000000007;
        return;
    }
    else if(n<2)
    {
        return;
    }
    if(n%2==0)
    {
        cs(n-1,j);
        cs(n-2,j);
    }
    else
    {
        cs(n-3,j);
        cs(n-4,j);
    }
}
int main()
{
    int n,j=0;
    cin>>n;
    cs(n,j);
    cout<return 0;
}

但是提交后它超时了

它数据太大了，以这种方法就显得力不从心。
请问有什么更快的解决方法吗？

递归效率比较低，可以用动态规划。大概思路：定义数组a[n]，用于存放方案数，a[2]和a[3]赋值1，其余为0。i从4到n遍历，根据i的奇偶性，将a[i]赋值为a[i-1]+a[i-2]，或者a[i-3]+a[i-4]。
c代码：

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

void cs(int n, int &j) {
    if (n > 3) {
        int a[n] = {0, 1, 1}, i;
        for (i = 4; i <= n; i++) {
            if (i % 2) {
                a[i - 1] = (a[i - 4] + a[i - 5]) % 1000000007;
            } else {
                a[i - 1] = (a[i - 2] + a[i - 3]) % 1000000007;
            }
        }
        j= a[n - 1];
    }else{
        j= n<2?0:1;
    }
}

int main() {
    int n,j;
    cin >> n;
    cs(n,j);
    cout << j;
    return 0;
}

执行结果：

这题确实应该用递归，但是不是你这样递归法，你这样太慢了
当你站在第n级台阶上，你有两种方案，一次跳a个或者一次跳b个，那么在第n级台阶上到达终点的所有可能性就等于跳a个的可能数量+跳b个的可能数量，最终你跳到距离终点只有2或者3的位置就只剩下1种可能了
或者换句话说，在每一个楼梯上，可能性数量其实早已经固定了，只不过一开始你并不知道这个数字到底是什么
就好像斐波那契数列，看起来没规律，其实有规律，并且在确定的位置上有确定的数字
你用递归的方式先从n开始找一直找回0是可以的，或者反过来先从0的位置循环一直循环到n也是可以的，楼梯数量足够少的话还是能够找到规律的