View Code of Problem 1059

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;
const int maxn = 105;

int n,p,m,t;
int dp[maxn][maxn];

int dfs(int cur,int time){
    if(dp[cur][time] != -1) return dp[cur][time];
    if(time == 0){
        if(cur == t) return dp[cur][time] = 1;
        else return dp[cur][time] = 0;
    }
    int res = 0;
    if(cur != 1) res += dfs(cur-1,time-1);
    if(cur != n) res += dfs(cur+1,time-1);
    return dp[cur][time] = res;
}

int main(){
    while(~scanf("%d%d%d%d",&n,&p,&m,&t)){
        memset(dp,-1,sizeof(dp));
        printf("%d\n",dfs(p,m));
    }
    return 0;
}