暴力递归——动态规划——状态压缩

import java.util.Scanner;

public class Main{
public static int mod = (int)1e9+7;
//暴力递归的解法
public static int walk(int N, int cur, int rest, int P){
//递归终止条件
if(rest == 0){
return cur == P ? 1 : 0;
}
if(cur == 1){
return walk(N,2,rest-1,P);
}
if(cur == N){
return walk(N,N-1,rest-1,P);
}
return walk(N,cur-1,rest-1,P) + walk(N,cur+1,rest-1,P);
}

public static int ways1(int N, int M, int K, int P){
    if(N < 2 || M < 1 || M > N || K < 1 || P < 1 || P > N){
        return 0;
    }
    return walk(N, M, K, P);
}

//暴力递归————————动态规划
public static int ways2(int N, int M, int K, int P){
    if(N < 2 || M < 1 || M > N || K < 1 || P < 1 || P > N){
        return 0;
    }
    //dp[rest][cur]
    int[][] dp = new int[K+1][N+1];
    dp[0][P] = 1;
    for(int i = 1; i <= K; i++){
        for(int j = 1; j <= N; j++){
            if(j == 1){
                dp[i][1] = dp[i-1][2] % mod;
            }else if(j == N){
                dp[i][j] = dp[i-1][N-1] % mod;
            }else{
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % mod;
            }
        }
    }
    return dp[K][M] % mod;
}
//动态规划，状态压缩
    public static int ways3(int N, int M, int K, int P){
    if(N < 2 || M < 1 || M > N || K < 1 || P < 1 || P > N){
        return 0;
    }
    //dp[rest][cur]
       //这里状态压缩记住一个规律，外循环是dp[i-1][j-1];在内循环中用变量tmp = dp[j]存储
    int[] dp = new int[N+1];
    dp[P] = 1;
    for(int i = 1; i <= K; i++){
        //外循环定义变量
        int leftUp = 0;
        //在内循环中，leftUp每一次都是上次循环的值，也即dp[j-1]
        for(int j = 1; j <= N; j++){
            int tmp = dp[j];//内循环找临时变量存储变量
            if(j == 1){
                dp[j] = dp[j+1] % mod;
            }else if(j == N){
                dp[j] = leftUp % mod;
            }else{
                dp[j] = (leftUp + dp[j+1]) % mod;
            }
            leftUp = tmp;
        }
    }
    return dp[M] % mod;
}

public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    int K = sc.nextInt();
    int P = sc.nextInt();
    System.out.println(ways3(N,M,K,P));
}

}