题面:
LeetCode 1306
思路:
只要能跳到其中一个0即可,和跳跃游戏1/2完全不同了,记忆化暴搜即可。
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( n ) 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;
}