1306.跳跃游戏 III：深度优先搜索(DFS)

【LetMeFly】1306.跳跃游戏 III：深度优先搜索(DFS)

力扣题目链接：https://leetcode.cn/problems/jump-game-iii/

这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。

请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。

注意，不管是什么情况下，你都无法跳到数组之外。

 

示例 1：

输入：arr = [4,2,3,0,3,1,2], start = 5
输出：true
解释：
到达值为 0 的下标 3 有以下可能方案： 
下标 5 -> 下标 4 -> 下标 1 -> 下标 3 
下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3 

示例 2：

输入：arr = [4,2,3,0,3,1,2], start = 0
输出：true 
解释：
到达值为 0 的下标 3 有以下可能方案： 
下标 0 -> 下标 4 -> 下标 1 -> 下标 3

示例 3：

输入：arr = [3,0,2,1,2], start = 2
输出：false
解释：无法到达值为 0 的下标 1 处。 

 

提示：

• 1 <= arr.length <= 5 * 10^4
• 0 <= arr[i] < arr.length
• 0 <= start < arr.length

解题方法：深度优先搜索

使用一个布尔类型的数组记录每个下标是否被搜索过，写一个dfs(start)函数返回从下标start能否到达一个值为$0$的下标。

dfs函数写法：

若start被访问过，说明从start无法到达值为$0$的下标，直接返回false；否则将start标记为被访问过并继续：

• 如果start - arr[start] ≥ 0并且dfs(start - arr[start])为true，则说明start可以通过下标start - arr[start]到达值为$0$的下标，返回true；
• 如果start + arr[start] < n并且dfs(start + arr[start])为true，则说明start可以通过下标start + arr[start]到达值为$0$的下标，返回true。

若两个路径都不可达，则返回false。

• 时间复杂度$O(len(arr))$，每个下标只会被递归至多一次。
• 空间复杂度$O(len(arr))$

AC代码

Python

'''
LastEditTime: 2026-05-17 10:46:40
'''
from typing import List

class Solution:
    def dfs(self, start: int) -> bool:
        if self.visited[start]:
            return False
        self.visited[start] = True
        if not self.arr[start]:
            return True
        if start - self.arr[start] >= 0 and self.dfs(start - self.arr[start]):
            return True
        if start + self.arr[start] < len(self.arr) and self.dfs(start + self.arr[start]):
            return True
        return False
    
    def canReach(self, arr: List[int], start: int) -> bool:
        self.arr = arr
        self.visited = [False] * len(arr)
        return self.dfs(start)

C++

/*
 * @LastEditTime: 2026-05-17 10:40:03
 */
class Solution {
private:
    vector<bool> visited;

    bool dfs(vector<int>& arr, int start) {
        if (visited[start]) {
            return false;
        }
        if (!arr[start]) {
            return true;
        }
        visited[start] = true;
        if (start - arr[start] >= 0 && dfs(arr, start - arr[start])) {
            return true;
        }
        if (start + arr[start] < arr.size() && dfs(arr, start + arr[start])) {
            return true;
        }
        return false;
    }
public:
    bool canReach(vector<int>& arr, int start) {
        visited.resize(arr.size());
        return dfs(arr, start);
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源