题目

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

问题分析

我们需要通过机器人在一维数组中从初始位置 $M$ 出发，经过 $K$ 步，最终到达位置 $P$。每一步，机器人要么向左走，要么向右走，但是有一些约束条件：

• 如果机器人当前在位置 1，它只能向右走；
• 如果机器人当前在位置 N，它只能向左走；
• 如果机器人在中间的任意位置，它可以选择向左或向右走。

问题的目的是求出从位置 $M$ 出发，经过 $K$ 步，最终到达位置 $P$ 的所有可能路径数。

核心思想

该问题本质上是一个 状态转移 问题，可以使用动态规划来优化暴力解法。我们需要考虑：

• 机器人在某一时刻的位置。
• 机器人当前步数。
• 机器人是否能通过这一步合法到达目标位置。

动态规划的定义

我们可以定义一个二维数组 dp[i][j]，表示在经过 i 步后，机器人处于位置 j 的方法数。最终的结果就是 dp[K][P]，即经过 $K$ 步到达位置 $P$ 的方法数。

递归暴力解法

递归的思路是从当前位置 $pos$ 出发，通过递归的方式尝试每一步向左或者向右走，直到走满 $K$ 步。递归的终止条件是步数达到 $K$ 或者当前位置越界。

递归暴力解法代码

public class RobotPaths {

    // 递归暴力解法
	public static int ways1(int N, int M, int P, int K) {
		if (N < 2 || M < 1 || M > N || P < 1 || P > N || K < 1) {
			return -1;
		}
		return process1(M, K, P, N);
	}

	/**
     * @param M 机器人当前来到的位置
     * @param K 机器人还有 K 步需要去走
     * @param P 最终的目标
     * @param N 路径长度
     * @return 机器人从 M 出发，走过 K 步之后，最终停在 P 有
     */
    public static int process(int M, int K, int P, int N) {
        if (K == 0) { // 剩余步数为0，已经不需要走了，走完了！
            return M == P ? 1 : 0;
        }
        if (M == 1) { // 1 -> 2 //情况1:当前位置cur在最左边界形态 向右走
            return process1(2, K - 1, P, N); // 下步就是当前位置current向右来到2 剩余步数rest-1
        }
        if (M == N) { // N-1 <- N //情况2:当前位置cur在最右边界形态 向左走
            return process1(N - 1, K - 1, P, N); // 下步就是当前位置current往左来到N-1 剩余步数rest-1
        }
        // 情况3:当前位置cur 既不在最左边也不在最右边时，也就是处于中间区域位置
        //    1.向左递归 左移cur-1 rest剩余步数-1 不断递归下一层深度 直到遇到basecase 剩余步数rest=0
        //    2.向右递归 右移cur+1 rest剩余步数-1 不断递归下一层深度 直到遇到basecase 剩余步数rest=0
        return process(M - 1, K - 1, P, N) + process(M + 1, K - 1, P, N);
    }
}

递归暴力解法分析

• 时间复杂度：由于递归的每一步都有两个选择（向左或向右），因此时间复杂度是指数级别的。具体来说，时间复杂度为 $O(2^K)$，这是因为每一层递归有两个分支，总共有 $K$ 层。
• 空间复杂度：递归的深度为 $K$，因此空间复杂度为 $O(K)$。

动态规划解法

为了优化递归暴力解法，我们可以使用 动态规划 来避免重复计算。定义一个二维数组 dp[i][j]，表示经过 $i$ 步后，机器人处于位置 $j$ 的方法数。

动态规划解法代码

public class RobotPaths {

	/**
	 * 动态规划解法
	 * @param N 一共多少个格子
	 * @param M 起始位置
	 * @param P 目标位置
	 * @param K 需要走多少步
	 * @return 多少种方法
	 */
	public static int ways2(int N, int M, int P, int K) {
	    if (N < 2 || M < 1 || M > N || P < 1 || P > N || K < 1) { //边界条件判断
	        return -1;
	    }
	    //初始化dp数组大小
	    int[][] dp = new int[N + 1][K + 1];
	
	    // dp[当前目标位置][还需要走0步] 没有剩余步数,此时机器人已经到达目标位置,记为1种方法
	    dp[P][0] = 1;
	    for (int rest = 1; rest <= K; rest++) { //从1出发遍历需要走k步
	        // 同上 情况1：最左边界（当前位置cur == 1）向右走
	        dp[1][rest] = dp[2][rest - 1]; // dp[当前位置cur==1][rest记录] = dp[当前目标位置2][还剩rest-1步需要走]
	
	        // 同上 情况2: 最右边界（当前位置cur == N）向左走
	        dp[N][rest] = dp[N - 1][rest - 1]; // dp[当前位置cur==N][rest记录] = dp[当前目标位置N-1][还剩rest-1步需要走]
	
	        // 同上 情况3：中间位置区域
	        for (int cur = 2; cur < N; cur++) {
	            // dp[当前位置cur在中间区域][rest记录] = dp[当前-1向左][剩rest-1步] + dp[当前+1向右][剩rest-1步] (向左/向右的和)
	            dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
	        }
	        
	    }
	    return dp[M][K]; // 返回从起始位置M，走K步后到达P的路径数
	}

    public static void main(String[] args) {
        // 示例：N = 5, M = 2, K = 3, P = 3
        int N = 5, M = 2, K = 3, P = 3;
        System.out.println(ways2(N, M, K, P)); // 输出方法数
    }
}

动态规划解法分析

• 时间复杂度：我们需要遍历所有的步数（$K$ 步）和所有的位置（$N$ 个位置），每个位置的计算只涉及到它相邻的位置。时间复杂度是 $O(K\times N)$。
• 空间复杂度：需要一个大小为 $(K+1)\times (N+1)$ 的二维数组来存储中间结果，因此空间复杂度是 $O(K\times N)$。

示例解析

假设有以下参数：

• $N=5$
• $M=2$
• $K=3$
• $P=3$

我们可以用动态规划的方式来计算：

我们使用一个二维数组 dp[i][j] 来表示从位置 i 出发，经过 j 步后能到达目标位置 P 的路径数。

计算完毕后dp 数组的状态如下：

dp = [
   [0, 0, 0, 0],
   [0, 0, 1, 0],  // dp[1][2] = 1
   [0, 1, 0, 3],  // dp[2][3] = 3
   [1, 0, 2, 0],  // dp[3][2] = 2
   [0, 1, 0, 2],  // dp[4][2] = 2
   [0, 0, 0, 0]
]

dp[2][3] = 3 表示从位置 2 走 3 步到达目标位置 3 有 3 条不同的路径，分别是：

• 2 -> 1 -> 2 -> 3
• 2 -> 3 -> 2 -> 3
• 2 -> 3 -> 4 -> 3

分析这 3 条路径：

第一条路径：2 -> 1 -> 2 -> 3
•	从 2 初始位置M出发
•	第一步向左走到 1（即：dp[1][2]）
•	第二步向右走到 2（即：dp[2][1]）
•	第三步向右走到 3（即：dp[3][0]）
第二条路径：2 -> 3 -> 2 -> 3
•	从 2 初始位置M出发
•	第一步向右走到 3（即：dp[3][1]）
•	第二步向左走到 2（即：dp[2][0]）
•	第三步向右走到 3（即：dp[3][0]）
第三条路径：2 -> 3 -> 4 -> 3
•	从 2 初始位置M出发
•	第一步向右走到 3（即：dp[3][1]）
•	第二步向右走到 4（即：dp[4][0]）
•	第三步向走走到 3（即：dp[3][0]）

这就是从位置 2 -> 1 -> 2 -> 3 的路径。

最终结果：
我们要的结果是从位置 2 走 3 步到达 3 的路径数，就是 dp[2][3]，它的值是3

小节

• 递归暴力解法：简单直接，适合理解问题，但时间复杂度为 $O(2^K)$，对于较大的 $K$ 不够高效。
• 动态规划解法：通过记忆化存储中间结果，大大提高了效率，时间复杂度为 $O(K\times N)$，适合处理更大规模的输入。