【搞定算法】机器人走路问题-蒲公英云

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

博主秋招提前批已拿百度、字节跳动、拼多多、顺丰等公司的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];
}