🎨  The ART of Dynamic Programming
\uD83C\uDFA8  The ART of Dynamic Programming\n\n1. All possibilities are considered via top-down brute-force depth-first-search\n2. Remember each subproblem\'s 
[\uD83C\uDFA8  The ART of Dynamic Programming](https://leetcode.com/discuss/general-discussion/712010/The-ART-of-Dynamic-Programming-An-Intuitive-Approach%3A-from-Apprentice-to-Master)\n\n1. **A**ll possibilities are considered via top-down brute-force depth-first-search\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n3. **T**urn the top-down solution upside-down to create the bottom-up solution\n\n**Note:** only the bottom-up solutions are AC (ie. top-down and top-down w/ memo each result in TLE)\n\n---\n\n**Kotlin Solutions:**\n\n1. **A**ll possibilities are considered via top-down brute-force depth-first-search\n\n```\nclass Solution {\n    fun canReach(s: String, lo: Int, hi: Int): Boolean {\n        var N = s.length\n        fun go(i: Int = 0): Boolean {\n            if (i == N - 1)                                 // \uD83D\uDED1 target reached\n                return true\n            for (j in i + lo..Math.min(i + hi, N - 1)) {    // \uD83D\uDE80 recusively consider all valid i..j hops\n                if (s[j] != \'0\')\n                    continue\n                if (go(j))                                  // \uD83C\uDFAF target reached from i..j hop\n                    return true\n            }\n            return false                                    // \u274C target not reachable from i\n        }\n        return go()\n    }\n}\n```\n\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n\n```\nclass Solution {\n    fun canReach(s: String, lo: Int, hi: Int): Boolean {\n        var m = mutableMapOf<Int, Boolean>()\n        var N = s.length\n        fun go(i: Int = 0): Boolean {\n            if (i == N - 1)                                 // \uD83D\uDED1 target reached\n                return true\n            if (m.contains(i))                              // \uD83E\uDD14 memo: ie. can we reach N - 1 from i?\n                return m[i]!!\n            for (j in i + lo..Math.min(i + hi, N - 1)) {    // \uD83D\uDE80 recusively consider all valid i..j hops\n                if (s[j] != \'0\')\n                    continue\n                if (go(j)) {                                // \uD83C\uDFAF target reached from i..j hop\n                    m[i] = true\n                    return true\n                }\n            }\n            m[i] = false\n            return false                                    // \u274C target not reachable from i\n        }\n        return go()\n    }\n}\n```\n\n3. **T**urn the top-down solution upside-down to create the bottom-up solution\n\n```\nclass Solution {\n    fun canReach(s: String, lo: Int, hi: Int): Boolean {\n        var N = s.length\n        var reach = Array<Boolean>(N) { false }\n        reach[N - 1] = true\n        for (j in N - 1 downTo 0) {\n            if (s[j] != \'0\' || !reach[j] || j - lo < 0)   // \uD83D\uDCA9 sanity checks: can only hop from valid reachable j down to i = j - lo..0 which can be a minimum of 0 (ie. 0 is the bottom-up target to reach starting from N - 1)\n                continue\n            for (i in j - lo downTo Math.max(0, j - hi))  // \uD83D\uDE80 we can reach each previous i from each current j as the recursive stack unwinds\n                reach[i] = true\n            if (reach[0])\n                return true                               // \uD83C\uDFAF target reached\n        }\n        return false                                      // \u274C target not reachable\n    }\n}\n```\n\n---\n\n**Javascript Solutions:**\n\n1. **A**ll possibilities are considered via top-down brute-force depth-first-search\n```\nlet canReach = (s, lo, hi) => {\n    let N = s.length;\n    let go = (i = 0) => {\n        if (s[i] == \'1\')                                         // \uD83D\uDEAB constraint per the problem statement\n            return false;\n        if (i == N - 1)                                          // \uD83D\uDED1 base case: we reached \uD83C\uDFAF target N - 1 \u2705\n            return true;\n        for (let j = i + lo; j <= Math.min(i + hi, N - 1); ++j)  // \uD83D\uDE80 recursively explore each i..j hop, ie. all possibilities\n            if (go(j))\n                return true;                                     // \uD83C\uDFAF propagate we reached target N - 1 \u2705\n        return false;                                            // \u274C target not reachable from i \uD83D\uDE41\n    };\n    return go();\n};\n```\n\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n```\nlet canReach = (s, lo, hi, m = new Map()) => {\n    let N = s.length;\n    let go = (i = 0) => {\n        if (s[i] == \'1\')                                         // \uD83D\uDEAB constraint per the problem statement\n            return false;\n        if (i == N - 1)                                          // \uD83D\uDED1 base case: we reached \uD83C\uDFAF target N - 1 \u2705\n            return true;\n        if (m.has(i))                                            // \uD83E\uDD14 memo\n            return m.get(i);\n        for (let j = i + lo; j <= Math.min(i + hi, N - 1); ++j)  // \uD83D\uDE80 recursively explore each i..j hop, ie. all possibilities\n            if (go(j))\n                return m.set(i, true)\n                        .set(j, true)\n                        .get(j);                                 // \uD83C\uDFAF propagate early: we reached target N - 1 \u2705\n        return m.set(i, false)\n                .get(i);                                         // \u274C target not reachable from i \uD83D\uDE41\n    };\n    return go();\n};\n```\n\n3. **T**urn the top-down solution upside-down to create the bottom-up solution\n```\nlet canReach = (s, lo, hi, m = new Map()) => {\n    let N = s.length;\n    let reach = Array(N).fill(false);                // \uD83E\uDD14 memo for reachability\n    reach[N - 1] = true;\n    for (let j = N - 1; 0 <= j; --j) {\n        if (!reach[j] || s[j] != \'0\' || j - lo < 0)  // \uD83E\uDD14 check bottom-up reachability + \uD83D\uDEAB constraint per the problem statement + \uD83D\uDCA9 DFS pruning to avoid TLE\n            continue;\n        let beg = Math.max(0, j - hi),\n            end = Math.min(j - lo, N - 1);\n        for (let i = beg; i <= end; ++i) {           // \uD83D\uDE80 we can reach each previous i from each current j as the recursive stack unwinds\n            if (s[i] == \'0\')\n                reach[i] = true;\n            if (reach[0])\n                return true;                         // \uD83C\uDFAF propagate early: we reached target 0 \u2705\n        }\n    }\n    return false;                                    // \u274C target not reachable \uD83D\uDE41\n};\n```\n\n---\n\n**Python3 Solutions:**\n\n\n1. **A**ll possibilities are considered via top-down brute-force depth-first-search\n```\nclass Solution:\n    def canReach(self, s: str, lo: int, hi: int) -> bool:\n        N = len(s)\n        def go(i = 0):\n            if not s[i] == \'0\':                                 # \uD83D\uDEAB problem statement constraint\n                return False\n            if i == N - 1:                                      # \uD83D\uDED1 base case: \u2705 we can reach target N - 1\n                return True\n            for j in range(i + lo, min(i + hi, N - 1) + 1):     # \uD83D\uDE80 recursively explore all i..j possibilities\n                if go(j):\n                    return True\n            return False\n        return go()\n```\n\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n```\nclass Solution:\n    def canReach(self, s: str, lo: int, hi: int) -> bool:\n        N = len(s)\n        @cache                                                  # \uD83E\uDD14 memo\n        def go(i = 0):\n            if not s[i] == \'0\':                                 # \uD83D\uDEAB problem statement constraint\n                return False\n            if i == N - 1:                                      # \uD83D\uDED1 base case: \u2705 we can reach target N - 1\n                return True\n            for j in range(i + lo, min(i + hi, N - 1) + 1):     # \uD83D\uDE80 recursively explore all i..j possibilities\n                if go(j):\n                    return True\n            return False\n        return go()\n```\n\n3. **T**urn the top-down solution upside-down to create the bottom-up solution\n```\nclass Solution:\n    def canReach(self, s: str, lo: int, hi: int) -> bool:\n        N = len(s)\n        dp = [False] * N                                      # \uD83E\uDD14 memo\n        dp[N - 1] = True                                      # \uD83D\uDED1 base case: \u2705 we can reach target N - 1\n        for j in range(N - 1, -1, -1):\n            if not s[j] == \'0\' or not dp[j] or j - lo < 0:    # \uD83D\uDEAB not (problem statement constraint) or not (is j reachable) or (out-of-bounds)\n                continue\n            beg = min(j - hi, N - 1)\n            end = max(0, j - lo)\n            for i in range(beg, end + 1):                     # \uD83D\uDE80 recursively explore all i..j possibilities (ie. as the recursive stack unwinds...)\n                if s[i] == \'0\':\n                    dp[i] = True\n            if dp[0]:\n                return True\n        return False\n```\n\n---\n\n**Initial notes from Contest 242 [ Virtual ] solve on May 25<sup>th</sup> 2021:**\n\n*Kotlin*\n```\n/*\n\nconstraint: You can move from index i to index j if the following conditions are fulfilled:\n\ni + lo <= j <= min(i + hi, N - 1) and s[j] == \'0\'.\n\ntarget: Return true if you can reach index s.length - 1 in s, or false otherwise.\n\n*/\n\n// TLE <-- explore all possibilities via brute-force DFS\n// class Solution {\n//     fun canReach(s: String, lo: Int, hi: Int): Boolean {\n//         var N = s.length\n//         var reach = Array<Boolean>(N) { false }\n//         fun go(i: Int = 0) {\n//             reach[i] = true\n//             for (j in i + lo..Math.min(i + hi, N - 1)) {\n//                 if (s[j] != \'0\')\n//                     continue\n//                 go(j)\n//             }\n//         }\n//         go()\n//         return reach[N - 1]\n//     }\n// }\n\n// sanity check, should TLE on large input -- ok as expected, now how should i memoize this properly without cutting myself short?  ie. i want to keep exploring until I reach N - 1, then I can return immediately?\n\n// i think i\'m kinda missing up bottom-up reach with top-down DFS, so simplify and focus\n\n// var reach = Array<Boolean>(N) { false }\n\n// ok now i\'m memoizing too many from each i..j candidates\n\n// add memo, ie. memoize hops from i..j\n\n\n// memory limit exceeded\n// class Solution {\n//     fun canReach(s: String, lo: Int, hi: Int): Boolean {\n//         var m = mutableMapOf<String, Boolean>()\n//         var N = s.length\n//         fun go(i: Int = 0): Boolean {\n//             if (i == N - 1)\n//                 return true\n//             for (j in i + lo..Math.min(i + hi, N - 1)) {\n//                 if (s[j] != \'0\')\n//                     continue\n//                 var key = "$i,$j"\n//                 if (m.contains(key))\n//                     return m[key]!!\n//                 if (go(j)) {\n//                     m[key] = true\n//                     return true\n//                 } else {\n//                     m[key] = false\n//                 }\n//             }\n//             return false\n//         }\n//         return go()\n//     }\n// }\n\n\n// ok since our range is from a window offset from each i of lo..hi, alot of those end ones overlap with same\n// so let\'s try dp reachability which was kinda my first intution which i mixed up with DFS brute-force check + memo\n\n// basically mimic the recursive stack unwinding in a favorable way, so we start with base case N - 1 is reachable and see if we can build a solution upon that to each the beginning from the end, this should save sufficient memory from memoizing each i..j forward-hop... instead do j..i back-hops\n\n/*\n\nconstraint: You can move from index i to index j if the following conditions are fulfilled:\n\ni + lo <= j <= min(i + hi, N - 1) and s[j] == \'0\'.\n\ntarget: Return true if you can reach index s.length - 1 in s, or false otherwise.\n\nso i compared to j is then\n\ni = j - lo until max(0, j - hi)\n\nExample 1:\n\nInput: s = "011010", minJump = 2, maxJump = 3\n            0123456\n            ii     \n               j\n               \nj = 3 can be reach from i = 0 and i = 1\n\nthus we search max(0, j - hi) .. max(0, j - lo) inclusive, let\'s fill this from \uD83D\uDC48 right-to-left\n\n3 - 3 = 0 .. 3 - 2 = 1\n\nie. from max(0, j - lo) down to max(0, j - hi)\n            \n            N = 6\nOutput: true\nExplanation:\nIn the first step, move from index 0 to index 3. \nIn the second step, move from index 3 to index 5.\n\ni wonder if this bottom-up implementation is correct for small inputs...\n\nno, its not, \n\n"01101110"\n2\n3\n\nreturn true <-- incorrect (i was allowing hops towards s[k] == \'1\' and non-reachable j which is not correct), so i fixed that and now i got the wrong answer...\n\n\nSubmission Result: Wrong Answer \nInput:\n"0000000000"\n 01234567890\n8\n8\n\nN = 10\n\nN - 1 = 9\n\n9 - 8 = 1\n\nso i can reach 1, but i cannot reach 0\n\nOutput:\ntrue\n\nExpected:\nfalse\n\nwe cannot hop from 9 to 0\n\ni\'m incorrectly considering candidates for k\n\n*/\n\n// AC: woo hoo!!! \uD83C\uDF89 \uD83E\uDD73\n\n// TODO: will solve this again tomorrow in another language to help solidify my understanding and add this onto the art of dynamic programming once completed in 4 languages [ Kt, Js, Py3, Cpp ] all using the same ART (all, remember, turn) formula, cheers! \uD83C\uDF7A\nclass Solution {\n    fun canReach(s: String, lo: Int, hi: Int): Boolean {\n        var N = s.length\n        var reach = Array<Boolean>(N) { false }\n        reach[N - 1] = true\n        for (j in N - 1 downTo 0) {\n            if (s[j] == \'1\' || !reach[j] || j - lo < 0) // \uD83D\uDCA9 sanity checks: oob check that next hop exceeds where we\'re at (j - lo < 0)\n                continue\n            for (k in Math.max(0, j - lo) downTo Math.max(0, j - hi))\n                if (s[k] == \'0\')\n                    reach[k] = true\n            if (reach[0])\n                return true\n        }\n        return false\n    }\n}\n```
[]