一、题目

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

二、题解

2.1 方法一：暴力递归

递归函数的设计

cur：机器人当前的位置 rest：机器人剩余的步数 aim：机器人的目标位置 N：一共1~N，N个位置
终止条件：当rest==0时，说明没有步数了，如果此时机器人所处的位置时目标位置，那么就返回一种方法，否则返回0
如果机器人处在1位置，那么机器人的下一个位置只能到2位置（从1位置走rest步到达aim的方法数等于从2位置走rest-1步到达aim的方法数,因为从1位置只能到2位置，没有其他选择）
如果机器人处在N位置，那么机器人的下一个位置只能到N-1位置（从N位置走rest步到达aim的方法数等于从N-1位置走rest-1步到达aim的方法数,因为从N位置只能到N-1位置，没有其他选择）
如果机器人处在中间位置，那么机器人下一步有两种选择，向左走一步或向右走一步(机器人处在中间位置走rest步到aim的方法数等于从cur-1走rest-1步到aim的方法数+从cur+1走rest-1步到aim的方法数)

源码：
✨

public static int process1(int cur,int rest,int aim,int N){
    if(rest==0){
       return cur==aim?1:0;
    }
    if(cur==1){
        return process1(2,rest-1,aim,N);
    }
    if(cur==N){
        return process1(N-1,rest-1,aim,N);
    }
   return process1(cur-1,rest-1,aim,N)+process1(cur+1,rest-1,aim,N);
}
    public static int ways1(int N,int start,int aim,int K){
        if(N<3 || start<1 || start>N || aim>N || aim<1 || K<1){
            return -1;
        }
    return  process1(start,K,aim,N);
    }

因为在上面这个暴力递归过程中出现了很多的重复调用，所以可以通过动态规划进行优化

2.2 方法二：从顶向下的动态规划（记忆化搜索）

思路：
使用缓存表
cur的范围是1~N
rest的范围是0~K
创建一个二维数组当作缓存表

对于算过的数据存储在这张表中，当再次需要计算这个数据的时候直接返回，避免了重复计算

源码：
💥

public static int process2(int cur,int rest,int aim,int N,int[][] dp){
    if(dp[cur][rest]!=-1){
        return dp[cur][rest];
    }
    int ans=-1;
    if(rest==0){
        ans=cur==aim?1:0;
    }else if(cur==1){
        ans=process2(2,rest-1,aim,N,dp);
    }else if(cur==N){
        ans=process2(N-1,rest-1,aim,N,dp);
    }else{
        ans=process2(cur+1,rest-1,aim,N,dp)+process2(cur-1,rest-1,aim,N,dp);
    }
    dp[cur][rest]=ans;
    return ans;
    }

    public static int ways2(int N,int start,int aim,int K) {
        if(N<3 || start<1 || start>N || aim>N || aim<1 || K<1){
            return -1;
        }
        int[][] dp=new int[N+1][K+1];
        for (int[] tmp:dp) {
            Arrays.fill(tmp,-1);
        }
        return  process2(start,K,aim,N,dp);
    }

2.3 方法三：最终的动态规划版本

通过寻找依赖关系将缓存表填满

源码：
💫

public static int ways3(int N,int start,int aim,int K) {
    if(N<3 || start<1 || start>N || aim>N || aim<1 || K<1){
        return -1;
    }
        int[][] dp=new int[N+1][K+1];
       dp[aim][0]=1;

        for (int rest= 1; rest<=K ; rest++) {
        dp[1][rest]=dp[2][rest-1]; //第一行手动赋值
            for (int cur = 2; cur <N ; cur++) {
                dp[cur][rest]=dp[cur+1][rest-1]+dp[cur-1][rest-1];
            }
            dp[N][rest]=dp[N-1][rest-1]; //第N行手动赋值
        }
       return dp[start][K];
    }