在华为OD机试的“跳房子2”问题中，目标是判断小红是否可以通过给定的步长数组 `steps` 跳到房子的最后一个格子，如果可以，还需要输出索引和最小的步数组合。以下是详细的解题思路和Python实现方法。 ### 解题思路 1. **问题建模**： - 小红从起点（位置0）开始跳跃，目标是到达位置 `count`。 - 每次跳跃的步长只能从 `steps` 数组中选择，跳跃后的位置必须在 `[0, count]` 的范围内。 - 要求找到一条跳跃路径，使得最终到达 `count` 的同时，所使用的步长索引之和最小。 2. **算法选择**： - 使用 **广度优先搜索（BFS）** 或 **动态规划（DP）** 来解决此类问题。 - BFS 更适合用于寻找最短路径或最小索引和的路径。 - 在 BFS 中维护一个队列，记录当前跳跃的位置和已经使用的步长索引集合，同时维护一个访问数组，避免重复处理相同状态。 3. **优化策略**： - 为了避免重复状态，使用一个数组 `visited` 记录到达每个位置时的最小索引和。 - 如果某个位置的索引和已经比当前路径更优，则无需继续扩展该路径。 4. **终止条件**： - 当 BFS 遍历到位置 `count` 时，即可返回当前路径的步长索引组合。 - 如果队列为空仍未找到目标位置，则返回无解。 ### Python 实现 ```python from collections import deque def jump_house(count, steps): n = len(steps) # visited[i] 表示到达位置 i 的最小索引和 visited = [float('inf')] * (count + 1) visited[0] = 0 # 起点索引和为0 # 队列保存 (当前位置, 当前索引和) queue = deque([(0, 0)]) while queue: pos, idx_sum = queue.popleft() for i, step in enumerate(steps): next_pos = pos + step next_idx_sum = idx_sum + i if next_pos > count: continue # 超出范围，跳过 if visited[next_pos] > next_idx_sum: visited[next_pos] = next_idx_sum queue.append((next_pos, next_idx_sum)) return visited[count] if visited[count] != float('inf') else -1 # 示例输入 count = 5 steps = [1, 2, 3] result = jump_house(count, steps) print("最小索引和为:", result) ``` ### 代码说明 - `visited` 数组用于存储到达每个位置时的最小索引和，避免重复计算。 - 使用 `deque` 实现 BFS，确保广度优先遍历。 - 每次跳跃后更新 `visited` 数组，只有当新的索引和更小时才继续扩展。 - 最终判断 `visited[count]` 是否为无穷大，决定是否可以到达终点。 ### 示例说明 - 输入：`count = 5`, `steps = [1, 2, 3]` - 输出：最小索引和为 `3`（路径为 0 → 1 → 3 → 5，索引分别为 0, 1, 2） ### 复杂度分析 - **时间复杂度**：`O(count * n)`，其中 `n` 是步长数组的长度。 - **空间复杂度**：`O(count)`，用于存储 `visited` 数组。