脚本宝典收集整理的这篇文章主要介绍了【leetcode】1306. Jump Game III，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

    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 

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        //递归 如果返回true需要短路其他的递归
        //不能返回去再去查找以前的位置
        int len=arr.size();
        vector<int>dp(len,0); //标记矩阵
        return digui(arr,dp,start,len);
        
    }
    bool digui(vector<int>& arr,vector<int>& dp,int index,int len){
        
        if(index<0 || index>=len) return false;
        if(arr[index]==0) return true;
        if(dp[index]==1) return false;
        dp[index]=1;
        return digui(arr,dp,index-arr[index],len) || digui(arr,dp,index+arr[index],len);
    }
};

脚本宝典总结

以上是脚本宝典为你收集整理的【leetcode】1306. Jump Game III全部内容，希望文章能够帮你解决【leetcode】1306. Jump Game III所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。