【搞定算法】机器人走路问题

浅浅的花香味﹌ 2021-11-22 03:50 314阅读 0赞

> 博主秋招提前批已拿百度、字节跳动、拼多多、顺丰等公司的offer，可加微信：**pcwl\_Java** 一起交流秋招面试经验，可获得博主的秋招简历和复习笔记。

> 给定四个参数N、P、M、K。表示：  
> N : 一共有1～N个位置  
> P : 一共有P步要走  
> M : 机器人初始停留在M位置上  
> K : 机器人想要去的位置是K  
> **题目：已知，如果机器人来到 1 位置，那么下一步一定会走到 2 位置。如果机器人来到 N 位置，那么下一步一定会走到 N - 1 位置；如果机器人在中间的位置，那么下一步既可以走向左，也可以走向右。请返回，机器人如果初始停留在 M 位置，经过 P 步之后，机器人来到 K 位置的走法有多少种。**

*  ###  递归实现 ###

public class RobotWork {
    
        /**
         * @param N ：共N个位置
         * @param M ：开始位置
         * @param P ：可以走的步数
         * @param K ： 目标位置
         * @return
         */
        public static int walk(int N, int M, int P, int K){
            if(P == 0){
                // basecase
                return M == K ? 1 : 0;
            }
            // 开始位置和结束位置只能往一个方向走
            if(M == 1){
                return walk(N, M + 1, P - 1, K);
            }else if(M == N){
                return walk(N, M - 1, P - 1, K);
            }
            // 向左走和向右走两种选择
            return walk(N, M + 1, P - 1, K) + walk(N, M - 1, P - 1, K);
        }
    }

*  ### 动态规划实现 ###

public class RobotWork {
    
        public static int walkDP(int N, int M, int P, int K){
            // 从递归的过程看：变量有 M 和 P
            int dp[][] = new int[N + 1][P + 1];
            // basecase：当在目标位置，还剩一步的时候
            dp[K][0] = 1;
            for(int j = 1; j <= P; j++){
                for(int i = 1; i <= N; i++){
                    if(i - 1 < 1){
                        // 在第一个位置上
                        dp[i][j] = dp[i + 1][j - 1];
                    }else if(i + 1 > N){
                        // 在最后一个位置上
                        dp[i][j] = dp[i - 1][j - 1];
                    }else{
                        dp[i][j] = dp[i + 1][j - 1] + dp[i - 1][j - 1];
                    }
                }
            }
            return dp[M][P];
        }
    }