0%

线性移动到指定位置

简介

假设有排成一行的 N 个位置, 记为 1~N, N 一定大于或等于 2, 开始时机器人在其中的 M 位置上 (M 一定是 1~N 中的一个) , 机器人可以往左走或者往右走, 如果机器人来到 1 位置, 那么下一步只能往右来到 2 位置;如果机器人来到 N 位置, 那么下一步只能往左来到 N-1 位置, 规定机器人必须走 K 步, 最终能来到 P 位置 (P 也一定是 1~N 中的一个) 的方法有多少种, 给定四个参数 N, M, K, P, 返回方法数

例如: N = 5, M = 2, K = 3, P = 3 有 3 种方法

  • 从 2 到 1, 从 1 到 2, 从 2 到 3
  • 从 2 到 3, 从 3 到 2, 从 2 到 3
  • 从 2 到 3, 从 3 到 4, 从 4 到 3

例如: N = 3, M = 1, K = 3, P = 3 有 0 种方法

分析

解决一个问题, 在没有明显的求解策略, 例如数学公式, 贪心策略等, 那么就通过尝试的方法找到答案

穷举法

由于要找出所有的可能性, 从正面分析就是简单递归计算出所有方法, 递归的结束逻辑就是判断在 K = 0 的时候判断当前是否在 P 点, 是的话该方法有效

线性移动的可能性如下

  • 当前位于起点, 只能向后移动
  • 当前位于终点, 只能向前移动
  • 位于其他点, 可以向前或向后移动

穷举过程需要涉及到剪枝处理, 因为参数中 N 和 P 是固定值, 所以当 M, K 相同时总会有相同的结果, 所以通过缓存进行处理

由于进行递归处理, 并且除了起点和终点外的每个位置都有左右两个方向变化, 深度为 K, 所以时间复杂度为 $O(2^K)$, 如果采用剪枝处理, 可以降低时间复杂度为 $(K^2)$, 需要额外的空间复杂度 $O(N \times K)$

因为剪枝的过程就是单纯的对计算结果进行缓存, 避免重复的递归过程

动态规划

通过上面的分析, 可以发现线性移动状态变化符合无后效性, 即对于某个特定状态后效的移动, 之前的决策都不会影响到

例如最开始的例子, 只要当前位置为 3, 并且还有 2 次移动的情况下, 就是只有 2 中方法, 不管之前的如何移动, 所以该递归状态符合无后效性

可以通过如下规则找到类似该问题的无后效性的动态规划方法

  • 通过明确可变参数代表一个递归状态, 这里指通过确定参数即可以确定返回值, 对应该问题的状态, 在固定的 N 和 P 中, 只要确定 M, K 总会得到明确的结果
  • 将上述的参数映射为状态集, 对应该问题就是通过二维数组表示在 M 位置, 剩余 K 步骤的时候总共有多少种方法
  • 找到当前可以明确的最终状态, 对应该问题就是在 K = 0 时, M 是否等于 P, 如果等于, 那么当前路径是正确的, 也就是 0, P 的值是 1
  • 找到执行过程方法, 对应该问题有多个逻辑
    • 当 M 为起点时, M 只能走向 2, 所以总共的方法就是 M = 2 并且剩余步骤为 K - 1 的状态的方法数
    • 当 M 为终点时, M 只能走向 N - 1, 所以总共的方法就是 M = N - 1 并且剩余步骤为 K - 1 的状态的方法数
    • 当 M 不为起点和终点时, 总共的方法就是 M - 1 并且剩余步骤为 K - 1 的状态的方法数加上 M + 1 并且剩余步骤为 K - 1 的状态的方法数的总和
  • 返回当前需要求的状态, 对应该问题知道这个状态就是 M, K

所以该解法处理的时间复杂度为 $O(N \times K)$

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
public class Test {
/**
* 模拟机器人步数
* 只能在 1 - N 的位置上移动, 当前在 cur 位置, 返回走完 rest 步后停在 P 位置的方法数
*
* @param N 位置为 1 - N, 固定参数
* @param cur 当前位置
* @param rest 还剩下的步数
* @param P 最终目标位置
* @return 方法数
*/
static int walk(int N, int cur, int rest, int P) {
// 通过缓存来进行剪枝
Integer w = Test.cache.get(cur + "-" + rest);
System.out.printf("%d, %d, %d\n", cur, rest, w);
if (w != null) {
return w;
}
// 如果没有剩余步数, 当前 cur 位置就是最后的位置
// 如果最后的位置停在 P 上, 那么当前移动方法是有效的, 反之无效
if (rest == 0) {
w = cur == P ? 1 : 0;
Test.cache.put(cur + "-" + rest, w);
return w;
}
// 如果还有 rest 步要走, 而当前的 cur 位置在 1 的位置上, 那么下一步只能走向 2
// 后续过程就是到 2 位置, 还有 rest - 1 步要走
if (cur == 1) {
w = walk(N, 2, rest - 1, P);
Test.cache.put(cur + "-" + rest, w);
return w;
}
// 如果还有 rest 步要走, 而当前的 cur 位置在 N 的位置上, 那么下一步只能走向 N - 1
// 后续过程就是到 N - 1 位置, 还有 rest - 1 步要走
if (cur == N) {
w = walk(N, N - 1, rest - 1, P);
Test.cache.put(cur + "-" + rest, w);
return w;
}
// 如果还有 rest 步要走, 当前的 cur 位置在非起始和终点位置, 那么可以向左右方向走
// 向左的后续就是到 cur - 1 的位置, 还有 rest - 1 步要走
// 向右的后续就是到 cur + 1 的位置, 还有 rest - 1 步要走
// 需要穷举所有的方法
w = walk(N, cur + 1, rest - 1, P) + walk(N, cur - 1, rest - 1, P);
Test.cache.put(cur + "-" + rest, w);
return w;
}

static HashMap<String, Integer> cache;

static int ways(int N, int M, int K, int P) {
// 无效的参数
if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
return 0;
}
cache = new HashMap<>();
// 总共 N 个位置, 从 M 点出发, 还剩下 K 步, 返回最终到达 P 点的方法数
return walk(N, M, K, P);
}

static int ways2(int N, int M, int K, int P) {
// 无效的参数
if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
return 0;
}
// K, M 是动态变化的, 构建二维数组映射递归状态
// 表示剩下 K 步时位置在 1 - N 的时候对应的方法
int[][] dp = new int[K + 1][N + 1];
// 很明确当剩下 0 步时, 只有位置在 P 的时候才是有效方法, 记为 1
dp[0][P] = 1;
for (int i = 1; i <= K; i ++) {
for (int j = 1; j <= N; j ++) {
if (j == 1) {
// 当位置在起点时, 当前位置只能向 2 走, 状态为步数 - 1, 2
dp[i][j] = dp[i - 1][2];
} else if (j == N) {
// 当位置在终点时, 当前位置只能向 N - 1 走, 状态为步数 - 1, N - 1
dp[i][j] = dp[i - 1][N - 1];
} else {
// 当位置在其他位置时, 为两种状态的和
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
}
}
System.out.println(Arrays.toString(dp[i]));
}
// 返回目标状态
return dp[K][M];
}

public static void main(String[] args) {
System.out.println(ways(5, 2, 3, 3));
System.out.println(ways(3, 1, 3, 3));
System.out.println(ways(7, 4, 9, 5));
System.out.println(ways2(5, 2, 3, 3));
System.out.println(ways2(3, 1, 3, 3));
System.out.println(ways2(7, 4, 9, 5));
}
}

结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
2, 3, null
3, 2, null
4, 1, null
5, 0, null
3, 0, null
2, 1, null
3, 0, 1
1, 0, null
1, 2, null
2, 1, 1
3
1, 3, null
2, 2, null
3, 1, null
2, 0, null
1, 1, null
2, 0, 0
0
4, 9, null
5, 8, null
6, 7, null
7, 6, null
6, 5, null
7, 4, null
6, 3, null
7, 2, null
6, 1, null
7, 0, null
5, 0, null
5, 2, null
6, 1, 1
4, 1, null
5, 0, 1
3, 0, null
5, 4, null
6, 3, 3
4, 3, null
5, 2, 2
3, 2, null
4, 1, 1
2, 1, null
3, 0, 0
1, 0, null
5, 6, null
6, 5, 9
4, 5, null
5, 4, 6
3, 4, null
4, 3, 3
2, 3, null
3, 2, 1
1, 2, null
2, 1, 0
4, 7, null
5, 6, 19
3, 6, null
4, 5, 10
2, 5, null
3, 4, 4
1, 4, null
2, 3, 1
3, 8, null
4, 7, 34
2, 7, null
3, 6, 15
1, 6, null
2, 5, 5
116
[0, 0, 1, 0, 1, 0]
[0, 1, 0, 2, 0, 1]
[0, 0, 3, 0, 3, 0]
3
[0, 0, 1, 0]
[0, 1, 0, 1]
[0, 0, 2, 0]
0
[0, 0, 0, 0, 1, 0, 1, 0]
[0, 0, 0, 1, 0, 2, 0, 1]
[0, 0, 1, 0, 3, 0, 3, 0]
[0, 1, 0, 4, 0, 6, 0, 3]
[0, 0, 5, 0, 10, 0, 9, 0]
[0, 5, 0, 15, 0, 19, 0, 9]
[0, 0, 20, 0, 34, 0, 28, 0]
[0, 20, 0, 54, 0, 62, 0, 28]
[0, 0, 74, 0, 116, 0, 90, 0]
116

Process finished with exit code 0