问题描述
Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach to any index with value 0.
Notice that you can not jump outside of the array at any time.
Example 1:
Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation: All possible ways to reach at index 3 with value 0 are: index 5 -> index 4 -> index 1 -> index 3 index 5 -> index 6 -> index 4 -> index 1 -> index 3
Example 2:
Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true
Explanation: One possible way to reach at index 3 with value 0 is: index 0 -> index 4 -> index 1 -> index 3
Example 3:
Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.
Constraints:
1 <= arr.length <= 5 * 10^40 <= arr[i] < arr.length0 <= start < arr.length
问题分析
按照题意，我们可利用dp求解；对于i而言，能否触达0点，取决于 i+arr[i] 和 i-arr[i] 这2个点至少有一个能否触达0点，即:
dp[i] = dp[i+arr[i]] || dp[i-arr[i]]
由于有2种跳跃方式，那么在递归过程中，可能会出现又跳回之前的点，从而造成回路，引起死循环；
因此我们在求解过程中利用负数标记法来记录已经跳过的点，这样在递归过程中，如果发现当前点值为负数，说明又跳回之前的点了，直接返回false即可
对于点i，2种跳跃方式都尝试后，再将点i重置为原有的值，进行回溯处理
综上，代码如下:
示例代码
func canReach(arr []int, start int) bool {
// 当前已经触达0，返回true
if arr[start] == 0 {
return true
}
// 若当前点为负数，说明是往回跳了，形成了回路，返回false
if arr[start] < 0 {
return false
}
ans := false
// 记录当前节点的初始值
absv := arr[start]
// 利用负数标记已访问
arr[start] = -1 * arr[start]
// case 1: 在数组范围内
if start+absv < len(arr) {
// 那么ans取决于 start+absv 是否能够触达0点
ans = ans || canReach(arr, start+absv)
if ans {
return ans
}
}
// case 2: 在数组范围内
if start-absv >= 0 && start-absv < len(arr) {
// 那么ans取决于 start-absv 是否能够触达0点
ans = ans || canReach(arr, start-absv)
if ans {
return ans
}
}
// 回溯处理，将当前值再改回原值
arr[start] = absv
return ans
}
func abs(n int) int {
if n < 0 {
return -1 * n
}
return n
}