EASY | 2 Approaches | DP (O(N)) | Binary Search (O(N log(N)) | C++
Approach 1 : \nWe use a DP + Sliding window :\n\n\nclass Solution {\npublic:\n    bool canReach(string s, int minJump, int maxJump) \n    {\n        if(s.back()
**Approach 1 : \nWe use a DP + Sliding window :**\n\n```\nclass Solution {\npublic:\n    bool canReach(string s, int minJump, int maxJump) \n    {\n        if(s.back() == \'1\')\n            return false;\n        \n        vector<bool> dp(s.size(), false);\n        dp[0] = true;\n        \n        int count = 0;\n        for(int i = 1; i < s.size(); ++i)\n        {\n            count += i >= minJump ? dp[i-minJump] : 0;\n            count -= i > maxJump ? dp[i-maxJump-1] : 0;\n            \n            if(count > 0 && s[i] == \'0\')\n                dp[i] = true;\n        }\n        if(dp.back())\n            return true;\n        return false;\n    }\n};\n```\n\n**Approach 2 :\nBinary Search O(N log(N))**\n\n```\nclass Solution {\npublic:\n    vector<int> index;\n    \n    bool can(int low, int high) // can we get previous index from which we can jump to current index\n    {\n        if(high < 0)\n            return false;\n        low = max(low, 0);\n        \n        int l = 0, r = index.size()-1, mid;\n        \n        while(r-l > 1)\n        {\n            mid = (r+l)/2;\n            \n            if(index[mid] >=low && index[mid] <= high)\n                return true;\n            \n            if(index[mid] < low)\n                l = mid;\n            else\n                r = mid;\n        }\n        if(index[l] >= low && index[l] <= high)\n            return true;\n        if(index[r] >= low && index[r] <= high)\n            return true;\n        return false;\n    }\n    \n    bool canReach(string s, int minJump, int maxJump) \n    {\n        if(s[0] != \'0\' || s.back() != \'0\')\n            return false;\n        \n        index.push_back(0);\n        for(int i = 1; i < s.size(); ++i)    \n            if(s[i] == \'0\' && can(i-maxJump, i-minJump))\n                index.push_back(i);\n        \n        if(index.back() == s.size()-1)\n            return true;\n        \n        return false;\n    }\n};\n```
['Dynamic Programming', 'C', 'Binary Tree', 'C++']