动态规划之机器人走路

题目假设有N个位置排成一行，记为1 ~ N，N必须在大一或等于2开始时机器人在M位置（M 一定是1 ~ N中的一个)如果机器人来到1位，下一步只能向右到2位。如果机器人来到N位，下一步只能向左到N-1位。如果机器人来到中间位置，然后下一步可以左走或者右走，规定机器人必须走K步，最后才能到达P位置(P也是1 ~ N中的一种方法有多少种？给定四个参数 N M K P，返回方法数方法是常规思路，递归求解

/** * * @param N  1 ~ N * @param M 当前位置 * @param K 要走的步数 * @param P 最后要去的地方 * @return */public static int walkWayOne(int N, int M, int K, int P){    if(N < 2 || M < 1 || M > N || K < 1 || P > N) { ///不成立        return -1;    }    return  processOne(N, M, K, P);}/** *  * @param N 有哪些位置 1 ~ N * @param cur 当前位置 * @param rest 还剩几步 * @param aim 目标位置 * @return */public static int processOne(int N, int cur, int rest, int aim){    if(rest == 0 && cur == aim){ ///有一个结果可以返回一个结果        return 1;    }    if(rest == 0 && cur != aim){ ///没有结果是0        return 0;    }    if(cur == 1){  //只能在一个位置右走        return processOne(N, 2, rest-1, aim);    }    if(cur == N){ //在N的位置只能左走        return processOne(N, N-1, rest-1, aim);    }    //中间位置可以左走右走    return processOne(N, cur - 1, rest-1, aim) + processOne(N, cur + 1, rest-1, aim);}

方法2动态规划解决方案，所谓的动态规划（也称为记忆搜索或自上而下的动态规划）是为了避免解决过程中某些解决方案的重复，使每个解决方案都是一个新的解决方案。如果每个子问题都不同，则无法优化动态规划。使用dp[cur][rest]二维数组记录，当前节点cur，剩余步数rest，求解值。下次直接返回使用

/** * * @param N 有哪些位置 1 ~ N * @param cur 当前位置 * @param rest 还剩几步 * @param aim 目标位置 * @param dp 动态规划数组，记录已解决的值 * @return */public static int processTwo(int N, int cur, int rest, int aim, int[][] dp){    if(dp[cur][rest] != -1){  ///已要求直接返回        return dp[cur][rest];    }    int ans = 0; //用来记录步数    if(rest == 0){        ans = cur == aim ? 1 : 0;    } else if (cur == 1) {        ans = processTwo(N, 2, rest -1, aim, dp);    } else if (cur == N) {        ans = processTwo(N, N-1, rest -1, aim, dp);    } else {        ans = ans = processTwo(N, cur - 1, rest -1, aim, dp) + processTwo(N, cur + 1, rest -1, aim, dp);;    }    dp[cur][rest] = ans;    return ans;}public static int walkWayTwo(int N, int M, int K, int P){    if(N < 2 || M < 1 || M > N || K < 1 || P > N) { ///不成立        return -1;    }    int[][] dp = new int[N + 1][K + 1];    ///初始化数组dp值-1    for (int i = 0; i < N + 1; i++) {        for (int j = 0; j < K + 1; j++) {            dp[i][j] = -1;        }    }    return  processTwo(N, M, K, P, dp);}

方法三对动态规划DP[cur][rest]从问题的意义分析可以看出，以N为基础 = 四、总步数K = 4.目标位置为3。例如，只有目标位置为3，剩余步数为0，方法数为1。当剩余步数为0，目标位置不为3时，方法数为0。当当当前位置为1时，只能向2位移动。当剩余步数减少到当前位置为N时，只能向N-1移动，剩余步数减一当前位置为其他位置时，要么左走，要么右走，剩余步数减一依赖如下：

dp表可根据依赖关系直接编写，使用时直接调用代码如下：

/** * * @param N  1 ~ N * @param M 当前位置 * @param K 要走的步数 * @param P 最后要去的地方 * @return */public static int walkWayThree(int N, int M, int K, int P){    if(N < 2 || M < 1 || M > N || K < 1 || P > N) { ///不成立        return -1;    }    int[][] dp = new int[N + 1][K + 1];    dp[P][0] = 1; //目前到达目标位置的P，剩下的走0步，此时有一种方法    ////根据规则直接写dp    for (int i = 1; i <= K; i++) {        for (int j = 1; j <= N; j++) {            if(j == 1){                dp[j][i] = dp[j+1][i-1];            } else if (j == N) {                dp[j][i] = dp[j - 1][i-1];            }else {                dp[j][i] = dp[j-1][i-1] + dp[j+1][i-1];            }        }    }    return  dp[M][K];}

总结测试代码

public class RobotWalk {    /**     *     * @param N  1 ~ N     * @param M 当前位置     * @param K 要走的步数     * @param P 最后要去的地方     * @return     */    public static int walkWayOne(int N, int M, int K, int P){        if(N < 2 || M < 1 || M > N || K < 1 || P > N) { ///不成立            return -1;        }        return  processOne(N, M, K, P);    }    /**     *     * @param N 有哪些位置 1 ~ N     * @param cur 当前位置     * @param rest 还剩几步     * @param aim 目标位置     * @return     */    public static int processOne(int N, int cur, int rest, int aim){        if(rest == 0 && cur == aim){ ///有一个结果可以返回一个结果            return 1;        }        if(rest == 0 && cur != aim){ ///没有结果是0            return 0;        }        if(cur == 1){  //只能在一个位置右走            return processOne(N, 2, rest-1, aim);        }        if(cur == N){ //在N的位置只能左走            return processOne(N, N-1, rest-1, aim);        }        //中间位置可以左走右走        return processOne(N, cur - 1, rest-1, aim) + processOne(N, cur + 1, rest-1, aim);    }    /**     *     * @param N 有哪些位置 1 ~ N     * @param cur 当前位置     * @param rest 还剩几步     * @param aim 目标位置     * @param dp 动态规划数组，记录已解决的值     * @return     */    public static int processTwo(int N, int cur, int rest, int aim, int[][] dp){        if(dp[cur][rest] != -1){  ///已要求直接返回            return dp[cur][rest];        }        int ans = 0; //用来记录步数        if(rest == 0){            ans = cur == aim ? 1 : 0;        } else if (cur == 1) {            ans = processTwo(N, 2, rest -1, aim, dp);        } else if (cur == N) {            ans = processTwo(N, N-1, rest -1, aim, dp);        } else {            ans = ans = processTwo(N, cur - 1, rest -1, aim, dp) + processTwo(N, cur + 1, rest -1, aim, dp);;        }        dp[cur][rest] = ans;        return ans;    }    /**     *     * @param N  1 ~ N     * @param M 当前位置     * @param K 要走的步数     * @param P 最后要去的地方     * @return     */    public static int walkWayTwo(int N, int M, int K, int P){        if(N < 2 || M < 1 || M > N || K < 1 || P > N) { ///不成立            return -1;        }        int[][] dp = new int[N + 1][K + 1];        ///初始化数组dp值-1        for (int i = 0; i < N + 1; i++) {            for (int j = 0; j < K + 1; j++) {                dp[i][j] = -1;            }        }        return  processTwo(N, M, K, P, dp);    }    /**     *     * @param N  1 ~ N     * @param M 当前位置     * @param K 要走的步数     * @param P 最后要去的地方     * @return     */    public static int walkWayThree(int N, int M, int K, int P){        if(N < 2 || M < 1 || M > N || K < 1 || P > N) { ///不成立            return -1;        }        int[][] dp = new int[N + 1][K + 1];        dp[P][0] = 1; //目前到达目标位置的P，剩下的走0步，此时有一种方法        ////根据规则直接写dp        for (int i = 1; i <= K; i++) {            for (int j = 1; j <= N; j++) {                if(j == 1){                    dp[j][i] = dp[j+1][i-1];                } else if (j == N) {                    dp[j][i] = dp[j - 1][i-1];                }else {                    dp[j][i] = dp[j-1][i-1] + dp[j+1][i-1];                }            }        }        return  dp[M][K];    }    public static void main(String[] args) {        int testTime = 1000;        System.out.println(“测试开始”;        for (int i = 0; i <= testTime; i++) {            int N = (int)(11 * Math.random());            int M = (int)((N+1) * Math.random());            int K = (int)((N+1) * Math.random());            int P =  (int)((N+1) * Math.random());            int resultOne = walkWayOne(N, M, K, P);            int resultTwo = walkWayTwo(N, M, K, P);            int resultThree = walkWayThree(N, M, K, P);            if(resultOne == resultTwo && resultThree == resultOne){                System.out.println(完美通过！！！！");            }else{                System.out.println(“对不起，有瑕疵！！！");            }        }    }}