🎨 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\nPreprocess the input to find the length of each `run` of same consecutive characters, then recursively "consume" each `run`.  This recursive "consuming" of characters is similar to [91. Decode Ways](https://leetcode.com/problems/decode-ways/discuss/117143/The-ART-of-Dynamic-Programming).\n\n---\n\n**Note:** if this `run` concept doesn\'t make sense, look at the supplemental solutions at the very bottom (they are verbosely how I started to solve this problem).\n\nWe can recursively consider "consuming":\n\na. one same consecutive character: `s[i]`\nb. two same consecutive characters: `s[i], s[i + 1]`\nc. three same consecutive characters: `s[i], s[i + 1], s[i + 2]`\nd. four same consecutive characters: `s[i], s[i + 1], s[i + 2], s[i + 3]` \uD83D\uDC48 (this use case is only applicable for characters `\'7\'` and `\'9\'`)\n\n---\n\n**Kotlin Solutions:**\n\n1. **A**ll possibilities are considered via top-down brute-force depth-first-search\n```\nclass Solution {\n    fun countTexts(s: String): Int {\n        var N = s.length\n        var run = IntArray(N) { 1 }\n        for (i in N - 2 downTo(0))\n            if (s[i] == s[i + 1])\n                run[i] = Math.min(1 + run[i + 1], if (s[i] == \'7\' || s[i] == \'9\') 4 else 3)\n        fun go(i: Int = 0): Int {\n            if (i == N)\n                return 1\n            var cnt = 0\n            for (k in 1..run[i])\n                if (i + k <= N)\n                    cnt += go(i + k)\n            return cnt\n        }\n        return go()\n    }\n}\n```\n\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n```\nclass Solution {\n    fun countTexts(s: String, m: MutableMap<Int, Int> = mutableMapOf<Int, Int>()): Int {\n        var N = s.length\n        var run = IntArray(N) { 1 }\n        for (i in N - 2 downTo(0))\n            if (s[i] == s[i + 1])\n                run[i] = Math.min(1 + run[i + 1], if (s[i] == \'7\' || s[i] == \'9\') 4 else 3)\n        fun go(i: Int = 0): Int {\n            if (i == N)\n                return 1\n            if (!m.contains(i)) {\n                var cnt = 0\n                for (k in 1..run[i])\n                    if (i + k <= N)\n                        cnt = (cnt + go(i + k)) % (1e9 + 7).toInt()\n                m[i] = cnt\n            }\n            return m[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```\nclass Solution {\n    fun countTexts(s: String, m: MutableMap<Int, Int> = mutableMapOf<Int, Int>()): Int {\n        var N = s.length\n        var run = IntArray(N) { 1 }\n        for (i in N - 2 downTo(0))\n            if (s[i] == s[i + 1])\n                run[i] = Math.min(1 + run[i + 1], if (s[i] == \'7\' || s[i] == \'9\') 4 else 3)\n        var dp = IntArray(N + 1) { 0 }\n        dp[N] = 1\n        for (i in N - 1 downTo 0)\n            for (k in 1..run[i])\n                if (i + k <= N)\n                    dp[i] = (dp[i] + dp[i + k]) % (1e9 + 7).toInt()\n        return dp[0]\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 countTexts = s => {\n    let N = s.length;\n    let run = Array(N).fill(1);\n    for (let i = N - 1; 0 <= i; --i)\n        if (s[i] == s[i + 1])\n            run[i] = Math.min(1 + run[i + 1], s[i] == \'7\' || s[i] == \'9\' ? 4 : 3);\n    let go = (i = 0, cnt = 0) => {\n        if (i == N)\n            return 1;\n        for (let k = 1; k <= run[i]; ++k)\n            if (i + k <= N)\n                cnt += go(i + k);\n        return cnt;\n    };\n    return go();\n};\n```\n\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n```\nlet countTexts = (s, m = new Map()) => {\n    let N = s.length;\n    let run = Array(N).fill(1);\n    for (let i = N - 1; 0 <= i; --i)\n        if (s[i] == s[i + 1])\n            run[i] = Math.min(1 + run[i + 1], s[i] == \'7\' || s[i] == \'9\' ? 4 : 3);\n    let go = (i = 0, cnt = 0) => {\n        if (i == N)\n            return 1;\n        if (!m.has(i)) {\n            for (let k = 1; k <= run[i]; ++k)\n                if (i + k <= N)\n                    cnt = (cnt + go(i + k)) % Number(1e9 + 7);\n            m.set(i, cnt);\n        }\n        return m.get(i);\n    };\n    return go();\n};\n```\n\n3. **T**urn the top-down solution upside-down to create the bottom-up solution\n```\nlet countTexts = (s, m = new Map()) => {\n    let N = s.length;\n    let run = Array(N).fill(1);\n    for (let i = N - 1; 0 <= i; --i)\n        if (s[i] == s[i + 1])\n            run[i] = Math.min(1 + run[i + 1], s[i] == \'7\' || s[i] == \'9\' ? 4 : 3);\n    let dp = Array(N + 1).fill(0);\n    dp[N] = 1;\n    for (let i = N - 1; 0 <= i; --i)\n        for (let k = 1; k <= run[i]; ++k)\n            if (i + k <= N)\n                dp[i] = (dp[i] + dp[i + k]) % Number(1e9 + 7);\n    return dp[0];\n};\n```\n\n---\n\n**Python3 Solutions:**\n\n1. **A**ll possibilities are considered via top-down brute-force depth-first-search\n```\nclass Solution:\n    def countTexts(self, s: str) -> int:\n        N = len(s)\n        run = [1] * N\n        for i in range(N - 2, -1, -1):\n            if s[i] == s[i + 1]:\n                run[i] = min(1 + run[i + 1], 4 if s[i] == \'7\' or s[i] == \'9\' else 3)\n        def go(i = 0, cnt = 0):\n            if i == N:\n                return 1\n            for k in range(1, run[i] + 1):\n                if i + k <= N:\n                    cnt = (cnt + go(i + k)) % int(1e9 + 7)\n            return cnt\n        return go()\n```\n\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n```\nclass Solution:\n    def countTexts(self, s: str) -> int:\n        N = len(s)\n        run = [1] * N\n        for i in range(N - 2, -1, -1):\n            if s[i] == s[i + 1]:\n                run[i] = min(1 + run[i + 1], 4 if s[i] == \'7\' or s[i] == \'9\' else 3)\n        @cache\n        def go(i = 0, cnt = 0):\n            if i == N:\n                return 1\n            for k in range(1, run[i] + 1):\n                if i + k <= N:\n                    cnt = (cnt + go(i + k)) % int(1e9 + 7)\n            return cnt\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 countTexts(self, s: str) -> int:\n        N = len(s)\n        run = [1] * N\n        for i in range(N - 2, -1, -1):\n            if s[i] == s[i + 1]:\n                run[i] = min(1 + run[i + 1], 4 if s[i] == \'7\' or s[i] == \'9\' else 3)\n        dp = [0] * (N + 1)\n        dp[N] = 1\n        for i in range(N - 1, -1, -1):\n            for k in range(1, run[i] + 1):\n                if i + k <= N:\n                    dp[i] = (dp[i] + dp[i + k]) % int(1e9 + 7)\n        return dp[0]\n```\n\n---\n\n**C++ Solutions:**\n\n1. **A**ll possibilities are considered via top-down brute-force depth-first-search\n```\nclass Solution {\npublic:\n    using VI = vector<int>;\n    using fun = function<int(int)>;\n    int countTexts(string s) {\n        int N = s.size();\n        VI run(N, 1);\n        for (auto i{ N - 2 }; 0 <= i; --i)\n            if (s[i] == s[i + 1])\n                run[i] = min(1 + run[i + 1], s[i] == \'7\' || s[i] == \'9\' ? 4 : 3);\n        fun go = [&](auto i) {\n            if (i == N)\n                return 1;\n            auto cnt = 0;\n            for (auto k{ 1 }; k <= run[i]; ++k)\n                if (i + k <= N)\n                    cnt = (cnt + go(i + k)) % int(1e9 + 7);\n            return cnt;\n        };\n        return go(0);\n    }\n};\n```\n\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n```\nclass Solution {\npublic:\n    using VI = vector<int>;\n    using fun = function<int(int)>;\n    using Map = unordered_map<int, int>;\n    int countTexts(string s, Map m = {}) {\n        int N = s.size();\n        VI run(N, 1);\n        for (auto i{ N - 2 }; 0 <= i; --i)\n            if (s[i] == s[i + 1])\n                run[i] = min(1 + run[i + 1], s[i] == \'7\' || s[i] == \'9\' ? 4 : 3);\n        fun go = [&](auto i) {\n            if (i == N)\n                return 1;\n            if (m.find(i) == m.end()) {\n                auto cnt = 0;\n                for (auto k{ 1 }; k <= run[i]; ++k)\n                    if (i + k <= N)\n                        cnt = (cnt + go(i + k)) % int(1e9 + 7);\n                m[i] = cnt;\n            }\n            return m[i];\n        };\n        return go(0);\n    }\n};\n```\n\n3. **T**urn the top-down solution upside-down to create the bottom-up solution\n```\nclass Solution {\npublic:\n    using VI = vector<int>;\n    using fun = function<int(int)>;\n    using Map = unordered_map<int, int>;\n    int countTexts(string s, Map m = {}) {\n        int N = s.size();\n        VI run(N, 1);\n        for (auto i{ N - 2 }; 0 <= i; --i)\n            if (s[i] == s[i + 1])\n                run[i] = min(1 + run[i + 1], s[i] == \'7\' || s[i] == \'9\' ? 4 : 3);\n        VI dp(N + 1, 0);\n        dp[N] = 1;\n        for (auto i{ N - 1 }; 0 <= i; --i)\n            for (auto k{ 1 }; k <= run[i]; ++k)\n                if (i + k <= N)\n                    dp[i] = (dp[i] + dp[i + k]) % int(1e9 + 7);\n        return dp[0];\n    }\n};\n```\n\n---\n\n**Supplemental Solutions:** the reason for the `run` preprocessing in the solutions above is because it simplifies this redundant and verbose code...\n\n1. **A**ll possibilities are considered via top-down brute-force depth-first-search\n```\nlet countTexts = s => {\n    let N = s.length;\n    let go = (i = 0) => {\n        if (i == N)\n            return 1;\n        let a = go(i + 1),\n            b = i + 1 < N && s[i] == s[i + 1] ? go(i + 2) : 0,\n            c = i + 2 < N && s[i] == s[i + 1] && s[i + 1] == s[i + 2] ? go(i + 3) : 0,\n            d = i + 3 < N && s[i] == s[i + 1] && s[i + 1] == s[i + 2] && s[i + 2] == s[i + 3] && (s[i] == \'7\' || s[i] == \'9\') ? go(i + 4) : 0;\n        return (a + b + c + d) % Number(1e9 + 7);\n    };\n    return go();\n};\n```\n\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n```\nlet countTexts = (s, m = new Map()) => {\n    let N = s.length;\n    let go = (i = 0) => {\n        if (i == N)\n            return 1;\n        if (!m.has(i)) {\n            let a = go(i + 1),\n                b = i + 1 < N && s[i] == s[i + 1] ? go(i + 2) : 0,\n                c = i + 2 < N && s[i] == s[i + 1] && s[i + 1] == s[i + 2] ? go(i + 3) : 0,\n                d = i + 3 < N && s[i] == s[i + 1] && s[i + 1] == s[i + 2] && s[i + 2] == s[i + 3] && (s[i] == \'7\' || s[i] == \'9\') ? go(i + 4) : 0;\n            m.set(i, (a + b + c + d) % Number(1e9 + 7));\n        }\n        return m.get(i);\n    };\n    return go();\n};\n```\n\n3. **T**urn the top-down solution upside-down to create the bottom-up solution\n```\nlet countTexts = s => {\n    let N = s.length;\n    let dp = Array(N + 1).fill(0);\n    dp[N] = 1;\n    for (let i = N - 1; 0 <= i; --i) {\n        let a = dp[i + 1],\n            b = i + 1 < N && s[i] == s[i + 1] ? dp[i + 2] : 0,\n            c = i + 2 < N && s[i] == s[i + 1] && s[i + 1] == s[i + 2] ? dp[i + 3] : 0,\n            d = i + 3 < N && s[i] == s[i + 1] && s[i + 1] == s[i + 2] && s[i + 2] == s[i + 3] && (s[i] == \'7\' || s[i] == \'9\') ? dp[i + 4] : 0;\n        dp[i] = (a + b + c + d) % Number(1e9 + 7);\n    }\n    return dp[0];\n};\n```\n
[]