机器人到达指定位置的方法数(递归/动态规划/空间压缩)

题目描述

假设有排成一行的N个位置，记为1~N，开始时机器人在M位置，机器人可以往左或者往右走，如果机器人在1位置，那么下一步机器人只能走到2位置，如果机器人在N位置，那么下一步机器人只能走到N-1位置。规定机器人只能走k步，最终能来到P位置的方法有多少种。由于方案数可能比较大，所以答案需要对1e9+7取模。

输入描述:

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

输出描述:

输出一个整数

示例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
说明
注意答案要取模

解题

import java.io.*;
import java.util.*;

public class Main{
    
    //定义一个模值，避免返回的结果过大
    private static final int MOD = (int)(1E9+7);
    
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] str = in.readLine().split(" ");
        int N = Integer.parseInt(str[0]);
        int M = Integer.parseInt(str[1]);
        int K = Integer.parseInt(str[2]);
        int P = Integer.parseInt(str[3]);
        
        System.out.print(getNum3(N,M,K,P));
    }
    
    //暴力递归搜索
    static int getNum(int N,int M,int K,int P){
        if(K==0)
            return M==P?1:0;
        if(M==1)
            return getNum(N,2,K-1,P);
        else if(M==N)
            return getNum(N,N-1,K-1,P);
        else
            return getNum(N,M-1,K-1,P)+getNum(N,M+1,K-1,P);
    }
    
    //将递归搜索转化成动态规划
    static int getNum2(int N,int M,int K,int P){
        //定义一个二维表
        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][j] = dp[i-1][j+1];
                else if(j==N)
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % MOD;
            }
        }
        return dp[K][M];
    }
    
    //对动态规划的二维表进行空间压缩
    static int getNum3(int N,int M,int K,int P){
        int[] dp = new int[N+1];
        dp[P] = 1;
        for(int i=1;i<=K;i++){
            int leftUp = dp[1];
            for(int j=1;j<=N;j++){
                int tmp = dp[j];
                if(j==1)
                    dp[j] = dp[j+1];
                else if(j==N)
                    dp[j] = leftUp;
                else
                    dp[j] = (leftUp+dp[j+1])%MOD;
                leftUp = tmp;
            }
        }
        return dp[M];
    }
   
}