1306. Jump Game III

use visited

T: O(n)
S: O(n)

```java
class Solution {
    public boolean canReach(int[] arr, int start) {
        return dfs(arr, start, new boolean[arr.length]);
    }
    private boolean dfs(int[] arr, int start, boolean[] visited) {
        if (start < 0 || start >= arr.length || visited[start]) {
            return false;
        }
        if (arr[start] == 0) {
            return true;
        }
        visited[start] = true;
        boolean result = dfs(arr, start + arr[start], visited) || dfs(arr, start - arr[start], visited);
        visited[start] = false;
        return result;
    }
}

/*

T: O(n)
S: O(n)

i + arr[i] or i - arr[i]

dp[i] is fixed, use memo[i], no...use visited && backtracking

base case: when arr[i] == 0

but this memo has 2 choice: i + arr[i] or i - arr[i]


find 0's index -> index 3

so start from 5

i + arr[i] or i - arr[i] -> reach 0

if (i < 0 || i >= arr.length) {
    return;
}
*/

```a

not use visited

make visited in negative, after dfs then backtracking back

|| arr[start] < 0


arr[start] = -arr[start];
...
arr[start] = -arr[start];

```java
class Solution {
    public boolean canReach(int[] arr, int start) {
        return dfs(arr, start, new boolean[arr.length]);
    }
    private boolean dfs(int[] arr, int start, boolean[] visited) {
        if (start < 0 || start >= arr.length || arr[start] < 0) {
            return false;
        }
        if (arr[start] == 0) {
            return true;
        }
        arr[start] = -arr[start];
        boolean result = dfs(arr, start + arr[start], visited) || dfs(arr, start - arr[start], visited);
        arr[start] = -arr[start];
        return result;
    }
}
```