算法刷题目动态规划
Source
Edit
History

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

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

一、题目

假设有排成一行的N个位置，记为1~N，开始时机器人在M位置，机器人可以往左或者往右走，如果机器人在1位置，那么下一步机器人只能走到2位置，如果机器人在N位置，那么下一步机器人只能走到N-1位置。规定机器人只能走k步，最终能来到P位置的方法有多少种

牛客网：https://www.nowcoder.com/questionTerminal/54679e44604f44d48d1bcadb1fe6eb61

二、思路+代码

1. 暴力递归

这类题目最简单、最容易想到的的方法是暴力递归。N 个位置，现在在 M 位置，走 K 步，到达 P 位置。那么

  • 当没有步数可以走时，也就是 rest 为 0 时，如果当前位置 cur 在 P 位置，那就返回 1，表示这条路可以通过
  • 当 cur 在 1 位置时，只能是 2 位置向左走过来的
  • 当 cur 在 N 位置时，只能是 N-1 位置向右走过来的
  • 当 cur 在其他位置时，可以是左边位置走过来的，也可以是右边位置走过来的

所以如下 暴力递归的方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 暴力递归
class Solution {
public:
    int way(int N, int M, int K, int P) {
        if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
            return 0;
        }
        return walk(N, M, K, P);
    }

private:
    int walk(int N, int cur, int rest, int p) {
        if (rest == 0) {
            return cur == p ? 1 : 0;
        }
        if (cur == 1) {
            return walk(N, 2, rest-1, p);
        }
        if (cur == N) {
            return walk(N, N-1, rest-1, p);
        }
        return walk(N, cur-1, rest-1, p) + walk(N, cur+1, rest-1, p);
    }
};

2. 动态规划

如上的暴力递归方案可以改成动态规划，我们发现递归函数的参数中 N 和 P 都是不变的。只有 cur 和 rest 在变化。我们去掉那些不变的参数，只用变化的参数来推演 walk 函数，我们发现满足如下条件：

  • walk(p, 0) = 1 ，其他的 walk(cur, 0) = 0
  • walk(1, rest) = walk(2, rest-1)
  • walk(N, rest) = walk(N-1, rest-1)
  • walk(cur, rest) = walk(cur-1, rest-1) + walk(cur+1, rest-1)

而且参数相同，也就是 cur 和 rest 相同时，结果一定是相同的，也就是说没有后效性。那么动态规划的方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution2 {
public:
    int way(int N, int M, int K, int P) {
        if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
            return 0;
        }
        std::vector<std::vector<int>> dp(K+1, std::vector<int>(N+1, 0));
        dp[0][P] = 1;
        for (size_t i = 1; i <= K; ++i) {
            for (size_t j = 1; j <= N; ++j) {
                if (j == 1) {
                    dp[i][1] = dp[i-1][2];
                } else if (j == N) {
                    dp[i][N] = dp[i-1][N-1];
                } else {
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1];
                }
            }
        }
        return dp[K][M];
    }
};

这种动态规划的方法还有优化的空间，waiting…