[LeetCode 1306] 跳跃游戏3(Ⅲ)

题面：

LeetCode 1306

思路：

只要能跳到其中一个0即可，和跳跃游戏1/2完全不同了，记忆化暴搜即可。
时间复杂度： $O(n)$
空间复杂度： $O(n)$

代码：

dfs

vector<bool> vis;void dfs(vector<int>& arr, vector<int>& ends, int start, int n, bool& ans) {if(ans) return ;if(!vis[start]) {vis[start] = true;if(find(ends.begin(), ends.end(), start) != ends.end()) {ans = true;return ;}if(start - arr[start] >= 0)dfs(arr, ends, start - arr[start], n, ans);if(start + arr[start] < n)dfs(arr, ends, start + arr[start], n, ans);}return ;
}bool canReach(vector<int>& arr, int start) {vector<int> ends;int n = arr.size();bool ans = false;vis = vector(n, false);for(int i = 0; i < n; ++i)if(arr[i] == 0)ends.push_back(i);if(ends.empty()) return ans;dfs(arr, ends, start, n, ans);return ans;
}