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

Question

c++跳楼梯问题如下

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

#include <bits/stdc++.h>
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<<j;
    return 0;
}

但是提交后它超时了

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

Answer 1

递归效率比较低，可以用动态规划。大概思路：定义数组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;
}

执行结果：