c++ O(n) dp
This problem is similar to sliding window max.\n\nBasic idea : \nstart from the end point.\nBase condition : dp[end] = true;\nMaintain a structure to store the 
This problem is similar to sliding window max.\n\nBasic idea : \nstart from the end point.\nBase condition : dp[end] = true;\nMaintain a structure to store the # of true and false in the ```[i + min, i + max]```\n\nFirst, I used unordered_set to do so, but it cause TLE.\nThen we can quickly figure out that a size 2 array is enough to represent the structrue.\n\n\n```\nclass Solution {\npublic:\n    bool canReach(string s, int mi, int ma) {\n        if(s.back() == \'1\') return false;\n        // build\n        int n = s.size();\n        vector<bool> dp(s.size(), false);\n        dp[n - 1] = true;\n        vector<int> S(2, 0); S[1]++; // 1 : true\n        \n        \n        // start\n        for(int i = n - 1 - mi; i >= 0; --i) {\n\t\t\t// *** to see if the sliding window contains TRUE\n            if(s[i] == \'0\' && S[1]) {\n                dp[i] = true;\n            }\n            else {\n                dp[i] = false;\n            }\n            \n            // update\n            ++S[dp[i + mi - 1]];\n            if(i + ma < s.size())\n                --S[dp[i + ma]];\n        }\n        \n        \n        return dp[0];\n    }\n};\n```
[]