一行中N个位置，机器人在M位置上，走K步，来到P位置--java实现

男娘i 2022-10-09 03:10 2阅读 0赞

详细描述：

假设有排成一行的N个位置，记为1-N，N一定大于或者等于2，开始时机器人在其中的M位置上（M一定是1-N中的一个）；

如果机器人来到1位置，那么下一步只能往右到2位置；

如果在N位置，下一步只能到N-1位置；

如果在中间位置，下一步可以往左或右；

规定机器人必须走K步，最终来到P位置（P在1-N之间）；

给定四个参数N、M、K、P，返回方法数。

解决方案的思想：

尝试入手：动态规划，重复操作都过滤掉，只留一次！

即暴力递归到动态规划的演变！

动态规划就是加缓存吗？不全对！

空间换时间，记忆化搜索！

从顶到下的动态规划！

这里我们分享三种解决方案：

1、暴力递归思想：核心代码实现如下

/**
 * @author wanghuainan
 * @date 2021/6/24 13:47
 */
 public class NanDaoRobotWalk {
 
 public static void main(String[] args) {
 /**
 * N 总共的位置数 N > 1
 * M 开始位置 0 < M < N + 1
 * P 最终的目标位置 0 1
 * M 开始位置 0 < M < N + 1
 * P 最终的目标位置 0 N || P < 1 || P > N || K < 1){
 return -1;
 }
 return process1(N,M,P,K);
 }
 
 /**
 * @param n
 * @param cur
 * @param p
 * @param rest
 * cur 范: 1 ~ N
 * rest 范：0 ~ K
 * @return
 */
 private static int process1(int n, int cur, int p, int rest) {
 if(rest == 0){
 return cur == p ? 1 : 0;
 }
 //位置在1时只能移动到2
 if(cur == 1){
 return process1(n,2,p,rest - 1);
 }
 //位置在n时只能移动到n-1
 if(cur == n){
 return process1(n,n - 1,p,rest - 1);
 }
 //位置在1到n之间时可以移动到cur+1或者cur-1
 return process1(n,cur + 1,p,rest - 1) + process1(n,cur - 1,p,rest - 1);
 }
 
 }

2、暴力递归到动态规划思想的演变思想：

2.1、如图所示

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70][]

定义一个二维数组，行代表N个数，列代表所移动的步数。？号的值来源于箭头处的值相加，属于动态规划思想。

2.2、结果图如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1][]

上图相加后的结果可以发现，数据很有规律，13就是二维数组的返回值。

2.3、核心代码实现如下

/**
 * @author wanghuainan
 * @date 2021/6/24 13:47
 */
 public class NanDaoRobotWalk {
 
 public static void main(String[] args) {
 /**
 * N 总共的位置数 N > 1
 * M 开始位置 0 < M < N + 1
 * P 最终的目标位置 0 1
 * M 开始位置 0 < M < N + 1
 * P 最终的目标位置 0 N || P < 1 || P > N || K < 1){
 return -1;
 }
 int[][] dp = new int[N + 1][K + 1];
 for(int i = 0;i <= N;i++){
 for(int j = 0;j <= K;j++){
 dp[i][j] = -1;
 }
 }
 return process2(N,M,P,K,dp);
 }
 
 private static int process2(int n, int cur, int p, int rest, int[][] dp) {
 if(dp[cur][rest] != -1){
 return dp[cur][rest];
 }
 int ans = 0;
 if(rest == 0){
 ans = cur == p ? 1 : 0;
 }else if(cur == 1){
 //位置在1时只能移动到2
 ans = process2(n,2,p,rest - 1,dp);
 }else if(cur == n){
 //位置在n时只能移动到n-1
 ans = process2(n,n - 1,p,rest - 1,dp);
 }else {
 //位置在1到n之间时可以移动到cur+1或者cur-1
 ans = process2(n,cur - 1,p,rest - 1,dp) + process2(n,cur + 1,p,rest - 1,dp);
 }
 dp[cur][rest] = ans;
 return ans;
 }
 
 
 }

3、标准动态规划思想：核心代码实现如下

/**
 * @author wanghuainan
 * @date 2021/6/24 13:47
 */
 public class NanDaoRobotWalk {
 
 public static void main(String[] args) {
 /**
 * N 总共的位置数 N > 1
 * M 开始位置 0 < M < N + 1
 * P 最终的目标位置 0 1
 * M 开始位置 0 < M < N + 1
 * P 最终的目标位置 0 N || P < 1 || P > N || K < 1){
 return -1;
 }
 int[][] dp = new int[N + 1][K + 1];
 dp[P][0] = 1;
 for(int rest = 1;rest <= K;rest++){
 //位置在1时只能移动到2
 dp[1][rest] = dp[2][rest - 1];
 for(int cur = 2;cur < N;cur++){
 //位置在1到n之间时可以移动到cur+1或者cur-1
 dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
 }
 //位置在n时只能移动到n-1
 dp[N][rest] = dp[N - 1][rest - 1];
 }
 return dp[M][K];
 }
 
 
 }

三种方案的执行结果：

![20210624193954749.png][]

到此，三种方案分享完毕，大家一定多测试、练习、多刷题，定会进步很快。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70]: /images/20221005/2fb86876394146cd86956ef420e21fcd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1]: /images/20221005/9cd50a3be75647e592d7e02ac458965d.png
[20210624193954749.png]: /images/20221005/6054129b526d4225a80bb0e3960eeecc.png