题解 | #机器人达到指定位置方法数#

//根据左边的暴力递归改出动态规划的版本
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,M,K,P;
    cin>>N>>M>>K>>P;//总的数目，起始位置，K步，终点位置
    int dp[N+1][K+1];//动态规划表
    for(int i=0;i<N+1;i++){
        for(int j=0;j<K+1;j++)
            dp[i][j]=0;
    }
    dp[P][0]=1;//第一列只有这个位置的数为1其它都为0 
    //dp表的填充顺序为从上到下从左到右按列优先填充 
    //并且对于第一行和最后一行的值要特殊处理
    for(int j=1;j<K+1;j++){
        for(int i=1;i<N+1;i++){
            if(i==1){//第一行
                dp[i][j]=dp[i+1][j-1];
                dp[i][j]=dp[i][j]%int(pow(10,9)+7);
            }
            else if(i==N){//最后一行 
                dp[i][j]=dp[i-1][j-1];
                dp[i][j]=dp[i][j]%int(pow(10,9)+7);
            }
            else{//普遍位置 
                dp[i][j]=dp[i-1][j-1]+dp[i+1][j-1];
                dp[i][j]=dp[i][j]%int(pow(10,9)+7);
            }
        }
    } 
//     for(int i=1;i<N+1;i++){
//         for(int j=0;j<K+1;j++)
//         {
//             cout<<dp[i][j]<<"     ";
//         }
//         cout<<endl;
//     }
    cout<<dp[M][K]%int(pow(10,9)+7)<<endl;
    return 0;
}