这题我的解法是使用状态机思维且看我下面的状态关系图：
这是我给出的三个状态，走一步用0状态表示，走一次两步用1状态表示，走两次两步用状态2表示，他们的转移关系如图
对图的解释：
1.走一步怎么转移过来的：可以选择继续走一步转移过来(如图中的自环)；走两步无论第一次还是第二次走两步，可以下一次走一步。
2.走一次两步怎么转移过来的： 可以走一步后选择走两步。
3.连续走两次两步怎么转移过来的： 可以走一次两步后再接着走两步。
1.状态定义
定义f [ i , j ] f[i,j]f[i,j],i ii 为此时是第几个台阶，j jj为此时的状态是走一步转移过来的(0)，还是连续两次走两步过来的(2)，还是只走一次两步过来的(1),此时的方案数为f [ i ] [ 0 ] + f [ i ] [ 1 ] + f [ i ] [ 2 ] f[i][0]+f[i][1]+f[i][2]f[i][0]+f[i][1]+f[i][2]
2.状态表示
根据状态图可以得出下面的转移式
1.f [ i ] [ 0 ] + = f [ i − 1 ] [ 0 ] + f [ i − 1 ] [ 2 ] + f [ i − 1 ] [ 1 ] ; f[i][0]+=f[i-1][0]+f[i-1][2]+f[i-1][1];f[i][0]+=f[i−1][0]+f[i−1][2]+f[i−1][1];
2.f [ i ] [ 1 ] + = f [ i − 2 ] [ 0 ] ; f[i][1]+=f[i-2][0];f[i][1]+=f[i−2][0];
3.f [ i ] [ 2 ] + = f [ i − 2 ] [ 1 ] ; f[i][2]+=f[i-2][1];f[i][2]+=f[i−2][1];
/********************************************************************* 程序名: 版权: Joecai 作者: Joecai 日期: 2022-03-27 21:17 说明: *********************************************************************/ #include <bits/stdc++.h> using namespace std; #define x first #define y second # define rep(i,be,en) for(int i=be;i<=en;i++) # define pre(i,be,en) for(int i=be;i>=en;i--) typedef pair<int, int> PII; #define ll long long #define endl "\n" #define LOCAL #define pb push_back const int N = 2e5 + 10, INF = 0x3f3f3f3f; int n; ll f[100][3]; void solve() { cin >> n; f[0][0] = 1; f[1][0] = 1; for (int i = 2; i <= n; i++) { f[i][0] += f[i - 1][0] + f[i - 1][2] + f[i - 1][1]; f[i][1] += f[i - 2][0]; f[i][2] += + f[i - 2][1]; } cout << f[n][0] + f[n][1] + f[n][2] << endl; } int main() { //std::ios::sync_with_stdio(false); //std::cin.tie(nullptr); //#ifdef LOCAL //freopen("data.in.txt","r",stdin); //freopen("data.out.txt","w",stdout); //#endif int __ = 1; //cin>>__; while (__--) { solve(); } return 0; }
点个赞走吧~
