一维dp, 时间:O(n*k), 空间O(n)
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define pii pair<int, int> #define pll pair<ll, ll> #define mp make_pair #define ios ios::sync_with_stdio(false); template <typename T> inline void read(T &x) { char ch = getchar(); int f = 1; x = 0; while (!isdigit(ch)) {if (ch == '-')f *= -1; ch = getchar();} while (isdigit(ch)) {x = (x<<1) + (x<<3) + (ch^48); ch = getchar();} x *= f; } ll qpow(ll x, ll y) { ll a = 1, b = x; while(y) {if(y&0x1) a*=b; b*=b; y>>=1;} return a; } int main(void) { #ifdef LOCAL ifstream cin("in.txt"); #endif const int MOD = 1e9 + 7; int n, m, k, p; cin >> n >> m >> k >> p; vector<int> dp(n+1, 0), ans(n+1, 0); // 首先初始化第一步的状态 if(m == 1) ans[2] = 1; else if(m == n) ans[n-1] = 1; else ans[m-1] = ans[m+1] = 1; // 从第二步开始计算 for(int cnt = 2; cnt <= k; cnt++) { dp = ans; // 保存上一步的状态,防止数据错乱 for(int i = 1; i <= n; i++) { if(i == 1) { if(dp[i+1] == 0) ans[i] = 0; // 表示这一步不能到达 else ans[i] += dp[i+1]; } else if(i == n) { if(dp[i-1] == 0) ans[i] = 0; // 表示这一步不能到达 else ans[i] += dp[i-1]; } else { if(dp[i-1] == 0 && dp[i+1] == 0) ans[i] = 0; // 表示这一步不能到达 else ans[i] += (dp[i-1] + dp[i+1]); } ans[i] = (ans[i] >= MOD) ? ans[i] - MOD : ans[i]; } } cout << ans[p] << endl; return 0; }