[数据结构与算法]Daimayuan Online Judge 走楼梯2

楼梯有 nn 阶，上楼可以一步上一阶，也可以一步上二阶。

但你不能连续三步都走两阶，计算走到第nn阶共有多少种不同的走法。

输入格式

一行，一个数字，表示nn。

输出格式

输出走楼梯的方式总数。

样例输入

6

样例输出

12

数据规模

对于100%100%的数据，保证n≤50n≤50。

思路：用dp来解，dp[i] [j]? ?i表示当前在第i个楼梯上，j表示连续2的个数。j小于3就符合要求。这个楼梯数大的是由小的转移过来的

完整代码：

#include <bits/stdc++.h>

using namespace std;

#define int long long
const int mod=1e9+7;

const int N=60;
int f[N][N];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    f[0][0]=1;
    for(int i=0;i<=n;i++)
    {
        f[i+1][0]+=f[i][0]+f[i][1]+f[i][2];//它本身的走法加上由2走来的（因为i+2可能会与i+1相同，所以用加法）
        f[i+2][1]+=f[i][0];
        f[i+2][2]+=f[i][1];
    }
    cout<<f[n][0]+f[n][1]+f[n][2]<<endl;
    return 0;
}