机器人到达指定位置的方法数问题

时间:2022-10-28 22:04:42

作者:Grey

原文地址:

博客园:机器人到达指定位置的方法数问题

CSDN:机器人到达指定位置的方法数问题

题目描述

链接:https://www.nowcoder.com/questionTerminal/54679e44604f44d48d1bcadb1fe6eb61
来源:牛客网

假设有排成一行的N个位置,记为1~N,开始时机器人在M位置,机器人可以往左或者往右走,如果机器人在1位置,那么下一步机器人只能走到2位置,如果机器人在N位置,那么下一步机器人只能走到N-1位置。规定机器人只能走k步,最终能来到P位置的方法有多少种。由于方案数可能比较大,所以答案需要对1e9+7取模。

暴力解

定义递归函数

long ways(int len, int start, int step, int end)

递归含义表示:机器人从坐标 start 开始,只能走 step 步,到达 end 的方法数是多少

接下来是 base case,

if (step == 0) {
    if (start == end) {
        return 1L;
    }
    return 0L;
}

如果 step 只剩下 0 步,说明没有步数可以走了,此时,如果 start == end ,表示正好就在目的地,返回一种方法数;

否则,返回 0 种方法数。

接下来是普遍情况,如果 start == 0,只能向右边走,即: ways(len, start + 1, step - 1, end)

如果 start == len - 1,只能向左边走,即:ways(len, start - 1, step - 1, end)

不在两端位置,则既可以向左边走,也可以向右边走,即:(ways(len, start - 1, step - 1, end) + ways(len, start + 1, step - 1, end))

暴力解法完整代码如下

    public static long ways(int len, int start, int step, int end) {
        if (step == 0) {
            if (start == end) {
                return 1L;
            }
            return 0L;
        }
        // step不止一步
        if (start == 0) {
            return ways(len, start + 1, step - 1, end);
        } else if (start == len - 1) {
            return ways(len, start - 1, step - 1, end);
        } else {
            return (ways(len, start - 1, step - 1, end) + ways(len, start + 1, step - 1, end));
        }
    }

超时

机器人到达指定位置的方法数问题

动态规划-缓存法(可 AC)

上述暴力递归过程,可变参数有两个 start,step;可以设置一个二维数组 dp,用于缓存递归中间过程的解,

long[][] dp = new long[len][step + 1];

dp[i][j]表示ways(len,i,j,end)的值,dp数组的值均初始化为 -1。

上述暴力递归过程增加这个 dp 参数,如果dp[i][j] != -1,则说明已经算过这个递归过程,直接返回dp[i][j]的值即可。

完整代码如下

    public static long ways(int len, int start, int step, int end) {
        long[][] dp = new long[len][step + 1];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j <= step; j++) {
                dp[i][j] = -1L;
            }
        }
        dp(len, start, step, end, dp);
        return dp[start][step];
    }

    private static long dp(int len, int start, int step, int end, long[][] dp) {
        if (dp[start][step] != -1L) {
            return dp[start][step] % MOD;
        }
        if (step == 0) {
            dp[start][step] = start == end ? 1L : 0L;
            return dp[start][step];
        }
        long ans;
        // step不止一步
        if (start == 0) {
            ans = dp(len, start + 1, step - 1, end, dp);
        } else if (start == len - 1) {
            ans = dp(len, start - 1, step - 1, end, dp);
        } else {
            ans = (dp(len, start - 1, step - 1, end, dp) + dp(len, start + 1, step - 1, end, dp));
        }
        dp[start][step] = ans;
        return ans;
    }

动态规划解-严格位置依赖(可 AC)

回到暴力递归解,伪代码如下

    public static long ways(int len, int start, int step, int end) {
        ……
        if (start == 0) {
            return ways(len, start + 1, step - 1, end);
        } else if (start == len - 1) {
            return ways(len, start - 1, step - 1, end);
        } else {
            return (ways(len, start - 1, step - 1, end) + ways(len, start + 1, step - 1, end));
        }
    }

根据缓存法得知,该递归过程使用一个二维数组 dp 即可存下所有结果,其中

dp[i][j]表示ways(len,i,j,end)的值,

通过观察上述暴力递归过程,dp[i][j]依赖的位置是dp[i+1][j-1]dp[i-1][j-1]

所以,依据上述递归过程,可以改成严格位置的动态规划版本,完整代码如下

    public static long ways(int len, int start, int step, int end) {
        long[][] dp = new long[len][step + 1];
        // 填好第0列
        dp[end][0] = 1L;
        for (int j = 1; j < step + 1; j++) {
            for (int i = 0; i < len; i++) {
                if (i == 0) {
                    dp[i][j] = dp[1][j - 1];
                } else if (i == len - 1) {
                    dp[i][j] = dp[len - 2][j - 1];
                } else {
                    dp[i][j] = dp[i - 1][j - 1] % MOD + dp[i + 1][j - 1] % MOD;
                }
            }
        }
        return dp[start][step];
    }

动态规划解-空间压缩版(可 AC)

通过上述严格位置的动态规划版本可以得知,dp[i][j]位置,依赖的位置是dp[i+1][j-1]dp[i-1][j-1],

示例图如下

机器人到达指定位置的方法数问题

而且,通过上述动态规划解,可以得知第 0 列中,除了dp[end][0] = 1L,其余都是 0,所以 dp 的第0列可以直接填充

机器人到达指定位置的方法数问题

所以,只需要用一个一维数组表示第 0 列,然后根据依赖关系,通过第 0 列推出第一列的值,一维数组此时表示第一列的值,依次这样递推下去,一直到最后一列,得解,这种方法就可以将二维数组压缩成一维数组,节省了空间复杂度。

完整代码如下

    public static long ways(int len, int start, int step, int end) {
        long[] dp = new long[len];
        dp[end] = 1L;
        long tmp = 0;
        for (int j = 1; j < step + 1; j++) {
            for (int i = 0; i < len; i++) {
                long ways = dp[i];
                if (i == 0) {
                    dp[i] = dp[1] % MOD;
                } else if (i == len - 1) {
                    dp[i] = tmp % MOD;
                } else {
                    dp[i] = tmp % MOD + dp[i + 1] % MOD;
                }
                tmp = ways;
            }
        }
        return dp[start];
    }

更多

算法和数据结构笔记