随笔记录

递归DP-机器人到达目的地方法数

2022-6-5 diaba 笔试题

package com.jiucaiyuan.net.question;

/**
 * @Author jiucaiyuan  2022/6/5 10:34
 * @mail services@jiucaiyuan.net
 */

public class Rabbit {

    /**
     * 给了一个固定值n，表示总共有多少个位置
     * 开始机器人在s位置上，每次可以迈一步，想要到达e位置，总共要走k步，有多少种走法可以到达e位置
     * 机器人可以往左走，也可以往右走
     *
     * @param n 总共位置数  1 2 3 4 ... n
     * @param s start开始位置（机器人开始停在s位置）
     * @param e end目标位置 （迈k步后，停留在e位置）
     * @param k 迈的步数 （机器人必须走k步）
     * @return 总共走法的种数
     */
    public static int walkWays(int n, int s, int e, int k) {
        return process(n, e, k, s);
    }

    /**
     * 暴力递归实现
     * 因为递归过程类似一个二叉树的遍历，高度为k，所以时间复杂度是 O(2^k)
     *
     * @param n    总共位置1 2 3 4 5 ... n
     * @param e    目标位置
     * @param rest 当前剩下的步数
     * @param curr 当前所在的位置
     * @return 当前的走法数目
     */
    public static int process(int n, int e, int rest, int curr) {
        //当前没有步骤可走了，如果在目标位置上，那么找到1中走法，如果没有在目标位置上，不是合法走法
        if (rest == 0) {
            return curr == e ? 1 : 0;
        }
        //如果当前位置在1，那么只能往2位置走
        if (rest == 1) {
            return process(n, e, rest - 1, 2);
        }
        //如果当前位置在n，那么下一步只能走到n-1
        if (rest == n) {
            return process(n, e, rest - 1, n - 1);
        }
        //如果不在第一个位置，也不在最后一个位置，那么可以向左走一步，也可以往右走一步
        return process(n, e, rest - 1, curr - 1) + process(n, e, rest - 1, curr + 1);
    }

    /**
     * 给了一个固定值n，表示总共有多少个位置
     * 开始机器人在s位置上，每次可以迈一步，想要到达e位置，总共要走k步，有多少种走法可以到达e位置
     * 机器人可以往左走，也可以往右走
     * 优化版本，暴力递归中重复的操作用缓存空间换时间的方式优化掉
     *
     * @param n 总共位置数  1 2 3 4 ... n
     * @param s start开始位置（机器人开始停在s位置）
     * @param e end目标位置 （迈k步后，停留在e位置）
     * @param k 迈的步数 （机器人必须走k步）
     * @return 总共走法的种数
     */
    public static int walkWaysV2(int n, int s, int e, int k) {
        int[][] dp = new int[k + 1][n + 1];
        for (int i = 0; i <= k; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = -1;
            }
        }
        return processV2(n, e, k, s, dp);
    }

    /**
     * 用空间换取暴力递归中重复计算的一些值
     * 时间复杂度: O(k*n)
     *
     * @param n    总共位置1 2 3 4 5 ... n
     * @param e    目标位置
     * @param rest 当前剩下的步数
     * @param curr 当前所在的位置
     * @param dp   计算过的值记录起来
     * @return 当前的走法数目
     */
    public static int processV2(int n, int e, int rest, int curr, int[][] dp) {
        if (dp[rest][curr] != -1) {
            return dp[rest][curr];
        }
        //当前没有步骤可走了，如果在目标位置上，那么找到1中走法，如果没有在目标位置上，不是合法走法
        if (rest == 0) {
            dp[rest][curr] = curr == e ? 1 : 0;
        } else if (rest == 1) {
            //如果当前位置在1，那么只能往2位置走
            dp[rest][curr] = process(n, e, rest - 1, 2);
        } else if (rest == n) {
            //如果当前位置在n，那么下一步只能走到n-1
            dp[rest][curr] = process(n, e, rest - 1, n - 1);
        } else {
            //如果不在第一个位置，也不在最后一个位置，那么可以向左走一步，也可以往右走一步
            dp[rest][curr] = process(n, e, rest - 1, curr - 1) + process(n, e, rest - 1, curr + 1);
        }
        return dp[rest][curr];
    }

    /**
     * 动态规划方式实现
     * 其实是分析上述递归过程，发现递归过程的规律，改为二维数组dp的前后联系，转化为dp二维数组的求解过程
     * （动态转移方程，其实就是上述递归的过程，也是分析尝试的过程）
     * 时间复杂度 O(k*n)
     *
     * @param n 总共可选位置1 2 3 4 ... n
     * @param e 目标位置
     * @param s 开始位置
     * @param k 需要移动步数
     * @return 返回走法数目
     */
    public static int dpWay(int n, int e, int s, int k) {
        int[][] dp = new int[k + 1][n + 1];
        dp[0][e] = 1;
        for (int rest = 1; rest <= k; rest++) {
            for (int curr = 1; curr <= n; curr++) {
                if (curr == 1) {
                    dp[rest][curr] = dp[rest - 1][2];
                } else if (curr == n) {
                    dp[rest][curr] = dp[rest - 1][curr - 1];
                } else {
                    dp[rest][curr] = dp[rest - 1][curr - 1] + dp[rest - 1][curr + 1];
                }
            }
        }
        return dp[s][k];
    }
}