LeetCode 题解工作台
跳跃游戏 V
给你一个整数数组 arr 和一个整数 d 。每一步你可以从下标 i 跳到： i + x ，其中 i + x 且 0 。 i - x ，其中 i - x >= 0 且 0 。 除此以外，你从下标 i 跳到下标 j 需要满足： arr[i] > arr[j] 且 arr[i] > arr[k] ，其中下…
3
题型
4
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们设计一个函数 ，表示从下标 开始跳跃能够访问的最大下标数。我们可以枚举 的所有合法的跳跃目标 ，即 $i - d \leq j \leq i + d$，并且 $arr[i] \gt arr[j]$。对于每个合法的 ，我们可以递归地计算 ，并取其中的最大值。最终的答案即为所有 的 的最大值。 我们可以使用记忆化搜索来优化这个过程，即使用一个数组 记录每个下标的 值，避免重复计算。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个整数数组 arr 和一个整数 d 。每一步你可以从下标 i 跳到：
i + x，其中i + x < arr.length且0 < x <= d。i - x，其中i - x >= 0且0 < x <= d。
除此以外，你从下标 i 跳到下标 j 需要满足：arr[i] > arr[j] 且 arr[i] > arr[k] ，其中下标 k 是所有 i 到 j 之间的数字（更正式的，min(i, j) < k < max(i, j)）。
你可以选择数组的任意下标开始跳跃。请你返回你 最多 可以访问多少个下标。
请注意，任何时刻你都不能跳到数组的外面。
示例 1：
输入：arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2 输出：4 解释：你可以从下标 10 出发，然后如上图依次经过 10 --> 8 --> 6 --> 7 。 注意，如果你从下标 6 开始，你只能跳到下标 7 处。你不能跳到下标 5 处因为 13 > 9 。你也不能跳到下标 4 处，因为下标 5 在下标 4 和 6 之间且 13 > 9 。 类似的，你不能从下标 3 处跳到下标 2 或者下标 1 处。
示例 2：
输入：arr = [3,3,3,3,3], d = 3 输出：1 解释：你可以从任意下标处开始且你永远无法跳到任何其他坐标。
示例 3：
输入：arr = [7,6,5,4,3,2,1], d = 1 输出：7 解释：从下标 0 处开始，你可以按照数值从大到小，访问所有的下标。
示例 4：
输入：arr = [7,1,7,1,7,1], d = 2 输出：2
示例 5：
输入：arr = [66], d = 1 输出：1
提示：
1 <= arr.length <= 10001 <= arr[i] <= 10^51 <= d <= arr.length
解题思路
方法一：记忆化搜索
我们设计一个函数 ，表示从下标 开始跳跃能够访问的最大下标数。我们可以枚举 的所有合法的跳跃目标 ，即 ，并且 。对于每个合法的 ，我们可以递归地计算 ，并取其中的最大值。最终的答案即为所有 的 的最大值。
我们可以使用记忆化搜索来优化这个过程，即使用一个数组 记录每个下标的 值，避免重复计算。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def maxJumps(self, arr: List[int], d: int) -> int:
@cache
def dfs(i):
ans = 1
for j in range(i - 1, -1, -1):
if i - j > d or arr[j] >= arr[i]:
break
ans = max(ans, 1 + dfs(j))
for j in range(i + 1, n):
if j - i > d or arr[j] >= arr[i]:
break
ans = max(ans, 1 + dfs(j))
return ans
n = len(arr)
return max(dfs(i) for i in range(n))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for knowledge of dynamic programming and its application to state transitions.
- question_mark
Check if the candidate understands how to optimize the solution with memoization.
- question_mark
Assess the ability to handle edge cases like arrays where no jumps are possible.
常见陷阱
外企场景- error
Not considering the valid jump conditions correctly, especially the intermediate indices.
- error
Misunderstanding how the jump distance `d` interacts with the array's constraints.
- error
Failing to optimize the solution with memoization, leading to inefficient repeated calculations.
进阶变体
外企场景- arrow_right_alt
Change the problem to allow multiple jump ranges and ask how to handle varying distances for each jump.
- arrow_right_alt
Introduce constraints where the jumps can only occur from certain indices and test how the solution adjusts.
- arrow_right_alt
Modify the problem to test if jumps can be made based on conditions other than values in the array (e.g., modulo operations).