【递推dp】B000_NK_走楼梯（三维记忆化）

小x一定要走到第 n 阶楼梯，每次都可以跨 1~m 步，且当前的跨步不能和前两部相同，小x有几种方案恰好走到第 n 阶楼梯

方法一：记忆化

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7, N=1e5+5;
int n, m, ans, f[N][10][10];

int dfs(int i, int p1, int p2) {
    if (i>n) return 0;
    if (i==n)return 1;
    if (f[i][p1][p2]!=-1) return f[i][p1][p2];
    int t=0;
    for (int j=1; j<=m; j++) if (j!=p1 && j!=p2) {
        t=(t+dfs(i+j, j, p1))%mod;
    }
    return f[i][p1][p1]=t;
}
int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    memset(f, -1, sizeof f);
    cout << dfs(0, 0, 0);
    return 0;
}

复杂度分析

• Time：\(O(nm)\)，
• Space：\(O(nm)\)