阿左：体系课18–暴力递归到dp

假设有排成一行的N个位置，记为1~N，N 一定大于或等于 2
开始时机器人在其中的M位置上(M 一定是 1~N 中的一个)
如果机器人来到1位置，那么下一步只能往右来到2位置；
如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；
如果机器人来到中间位置，那么下一步可以往左走或者往右走；
规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种
给定四个参数 N、M、K、P，返回方法数。

输入描述:
输出包括一行四个正整数N（2<=N<=5000）、M(1<=M<=N)、K(1<=K<=5000)、P(1<=P<=N)。

输出描述:
输出一个整数，代表最终走到P的方法数对取模后的值。
示例1
输入
5 2 3 3
输出
3
说明
1).2->1,1->2,2->3

2).2->3,3->2,2->3

3).2->3,3->4,4->3
示例2
输入
1000 1 1000 1
输出
591137401

#include <bits/stdc++.h>
using namespace std;
const int  N=5010;
const int  E=1e9+7;
int  dp[N][N];
int n,m,p,k;
//  站在u位置还剩r步走到p位置的方法数
int   dfs(int  u,int  r)
{
    if(dp[u][r]!=-1) return dp[u][r];
    int  res=0;
    if(r==0) 
          res=(u==p  ? 1:0);
    else if(u==1) res= dfs(2,r-1)%E;
    else if(u==n) res= dfs(n-1,r-1)%E;
    else
    {
        res=  (dfs(u-1,r-1)+dfs(u+1,r-1))%E;
    }
    dp[u][r]=res;
    return  res;

}
int main()
{
    memset(dp,-1,sizeof  dp);
    cin>>n>>m>>k>>p;
    cout<<dfs(m,k);


    return  0;
}