电梯谜题：最少按键次数 - 算法题解

题目描述

有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 (i) 层楼（(1 \le i \le N)）上有一个数字 (K_i)（(0 \le K_i \le N)）。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如： (3, 3, 1, 2, 5) 代表了 (K_i)（(K_1=3)，(K_2=3)，……），从 (1) 楼开始。在 (1) 楼，按“上”可以到 (4) 楼，按“下”是不起作用的，因为没有 (-2) 楼。那么，从 (A) 楼到 (B) 楼至少要按几次按钮呢？

输入格式

共二行。

第一行为三个用空格隔开的正整数，表示 (N, A, B)（(1 \le N \le 200)，(1 \le A, B \le N)）。

第二行为 (N) 个用空格隔开的非负整数，表示 (K_i)。

输出格式

一行，即最少按键次数，若无法到达，则输出 -1。

样例 #1

样例输入 #1

5 1 5
3 3 1 2 5

样例输出 #1

3

提示

对于 (100) % 的数据，(1 \le N \le 200)，(1 \le A, B \le N)，(0 \le K_i \le N)。

算法思路

本题可以使用动态规划来解决。我们定义 (dp[i]) 为从 (1) 楼到 (i) 楼的最少按键次数。那么，我们可以得到以下递推关系：

• 当 (i = 1) 时，(dp[i] = 0)。
• 当 (i > 1) 时，我们可以从 (i - K_i) 楼走到 (i) 楼，或者从 (i + K_i) 楼走到 (i) 楼。因此，(dp[i] = min(dp[i - K_i], dp[i + K_i]) + 1)。

需要注意的是，如果 (i - K_i) 或 (i + K_i) 不在 (1) 到 (N) 的范围内，则相应的 (dp) 值应该设为无穷大。

代码实现

N, A, B = map(int, input().split())
K = list(map(int, input().split()))

dp = [float('inf')] * (N + 1)
dp[1] = 0

for i in range(2, N + 1):
    if 1 <= i - K[i - 1] <= N:
        dp[i] = min(dp[i], dp[i - K[i - 1]] + 1)
    if 1 <= i + K[i - 1] <= N:
        dp[i] = min(dp[i], dp[i + K[i - 1]] + 1)

if dp[B] == float('inf'):
    print(-1)
else:
    print(dp[B])

测试用例

测试输入 #1

5 1 5
3 3 1 2 5

测试输出 #1

3

总结

本题考察了动态规划的应用。通过定义状态和推导出递推关系，我们可以有效地解决问题。需要注意的是，边界条件的处理是解决该类问题的重要环节。

希望以上解析能够帮助你更好地理解这道题目。