LeetCode 题解工作台
恰好移动 k 步到达某一位置的方法数目
给你两个 正 整数 startPos 和 endPos 。最初，你站在 无限 数轴上位置 startPos 处。在一步移动中，你可以向左或者向右移动一个位置。 给你一个正整数 k ，返回从 startPos 出发、 恰好 移动 k 步并到达 endPos 的 不同 方法数目。由于答案可能会很大，返回…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们设计一个函数 $dfs(i, j)$，表示当前位置距离目标位置的距离为 ，还剩 步，有多少种方法到达目标位置。那么答案就是 $dfs(abs(startPos - endPos), k)$。 函数 $dfs(i, j)$ 的计算方式如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你两个 正 整数 startPos 和 endPos 。最初，你站在 无限 数轴上位置 startPos 处。在一步移动中，你可以向左或者向右移动一个位置。
给你一个正整数 k ，返回从 startPos 出发、恰好 移动 k 步并到达 endPos 的 不同 方法数目。由于答案可能会很大，返回对 109 + 7 取余 的结果。
如果所执行移动的顺序不完全相同，则认为两种方法不同。
注意：数轴包含负整数。
示例 1：
输入：startPos = 1, endPos = 2, k = 3 输出：3 解释：存在 3 种从 1 到 2 且恰好移动 3 步的方法： - 1 -> 2 -> 3 -> 2. - 1 -> 2 -> 1 -> 2. - 1 -> 0 -> 1 -> 2. 可以证明不存在其他方法，所以返回 3 。
示例 2：
输入：startPos = 2, endPos = 5, k = 10 输出：0 解释：不存在从 2 到 5 且恰好移动 10 步的方法。
提示：
1 <= startPos, endPos, k <= 1000
解题思路
方法一：记忆化搜索
我们设计一个函数 ，表示当前位置距离目标位置的距离为 ，还剩 步，有多少种方法到达目标位置。那么答案就是 。
函数 的计算方式如下：
- 如果 或者 ，说明当前位置距离目标位置的距离大于剩余步数，或者剩余步数为负数，此时无法到达目标位置，返回 ；
- 如果 ，说明剩余步数为 ，此时只有当前位置距离目标位置的距离为 时才能到达目标位置，否则无法到达目标位置，返回 或者 ；
- 否则，当前位置距离目标位置的距离为 ，还剩 步，那么有两种方法到达目标位置：
- 向左移动一步，此时当前位置距离目标位置的距离为 ，还剩 步，方法数为 ；
- 向右移动一步，此时当前位置距离目标位置的距离为 ，还剩 步，方法数为 ；
- 最后，返回两种方法的和对 取余的结果。
为了避免重复计算，我们使用记忆化搜索，即使用一个二维数组 记录函数 的结果，当函数 被调用时，如果 不为 ，则直接返回 ，否则计算 的值，并返回 。
时间复杂度 ，空间复杂度 。其中 为题目给定的步数。
class Solution:
def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
@cache
def dfs(i: int, j: int) -> int:
if i > j or j < 0:
return 0
if j == 0:
return 1 if i == 0 else 0
return (dfs(i + 1, j - 1) + dfs(abs(i - 1), j - 1)) % mod
mod = 10**9 + 7
return dfs(abs(startPos - endPos), k)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate can handle dynamic programming approaches and optimizes for space and time efficiency.
- question_mark
The candidate shows an understanding of state transitions and can apply them effectively to solve combinatorics problems.
- question_mark
The candidate demonstrates the ability to handle modular arithmetic for large numbers, which is a key aspect of the problem.
常见陷阱
外企场景- error
Not handling the case where the number of left and right moves cannot sum to the required target difference.
- error
Overcomplicating the problem by not utilizing dynamic programming efficiently, resulting in unnecessary computations.
- error
Failing to apply the modulo operation at each step, leading to potential overflow or incorrect results.
进阶变体
外企场景- arrow_right_alt
Change the number of steps k to a larger value and analyze performance.
- arrow_right_alt
Introduce additional constraints, such as limiting the number of right or left moves.
- arrow_right_alt
Extend the problem to multidimensional grids, where you can move in more directions than just left or right.