题解与来源题共享。已有题解默认通过；新增或编辑后需由来源域管理员审核。待审核、驳回题解仅作者和审核管理员可见。来源域：system

• 0

  Asunaysn LV 8 MOD @ 2025-8-24 13:44:59

  $O(N^2)$ DP

  动态规划（DP）：

  定义 $dp[i][j]$ 表示走了 $i$ 步后到达位置 $j$ 的方法数。

  初始状态：$dp[0][M] = 1$（ $0$ 步时位于初始位置 $M$ ）。

  状态转移：

  如果当前位置 $j$ 是 $1$ （左边界），下一步只能走到 $2$ ： $dp[i+1][2] += dp[i][1]$

  如果当前位置 $j$ 是 $N$ （右边界），下一步只能走到 $N-1$ ： $dp[i+1][N-1] += dp[i][N]$

  对于中间位置 $j$ ，下一步可以走到 $j-1$ 或 $j+1$ ：$dp[i+1][j-1] += dp[i][j]，dp[i+1][j+1] += dp[i][j]$

  #include <bits/stdc++.h>
  using namespace std;
  const int mod = 1e9 + 7;
  int n, m, k, p;
  long long dp[1010][1010];
  int main() {
  	cin >> n >> m >> k >> p;
  	dp[0][m] = 1;
  	for (int i = 1; i <= k; i++) {
  		for (int j = 1; j <= n; j++) {
  			dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
  		}
  	}
  	cout << dp[k][p];
  	return 0;
  }
  
  

• 1