Javascript and C++ solutions
Synopsis:\n\n Recursive Top-Down solutions: let i and j be the indexes corresponding to the substring of s from i to j inclusive (ie. s[i..j])\n\t Base case: if
**Synopsis:**\n\n* **Recursive Top-Down solutions:** let `i` and `j` be the indexes corresponding to the substring of `s` from `i` to `j` inclusive (ie. `s[i..j]`)\n\t* Base case: if `i >= j` then return `0`\n\t* Recursive cases:\n\t\t* if `s[i] == s[j]` then return the solution for the sub-problem *without* the characters at `i` and `j` (since there\'s a match, there is no "penalty")\n\t\t* if `s[i] != s[j]` then return `1` plus the minimum solution of (the sub-problem *without* the character at `i`) or (the sub-problem *without* the character at `j`)\n\n* **DP Bottom-Up solutions:** Same idea as above, but finding solutions for each substring from right-to-left.  Let `dp[i][j]` denote the optimal solution for a substring from `i` to `j` non-inclusive (ie. `s[i..j)`).  The bottom-up solution starts with a substring of length `1` (ie. the right-most character) and builds upon itself till length `N`.  The answer is `dp[0][N]` (ie. the optimal solution for `s[0..N)`).\n\n**Javascript Solutions: Recursive Top-Down**\n\n*Javascript: TLE without memo*\n```\nlet minInsertions = s => {\n    let go = (s, i, j) => {\n        if (i >= j)\n            return 0;\n        if (s[i] == s[j])\n            return go(s, i + 1, j - 1);\n        return 1 + Math.min(go(s, i + 1, j), go(s, i, j - 1));\n    };\n    return go(s, 0, s.length - 1);\n};\n```\n\n*Javascript: with memo*\n```\nlet minInsertions = (s, memo = [...Array(501)].map(x => Array(501).fill(-1))) => {\n    let go = (s, i, j) => {\n        if (memo[i][j] > -1)\n            return memo[i][j];\n        if (i >= j)\n            return memo[i][j] = 0;\n        if (s[i] == s[j])\n            return memo[i][j] = go(s, i + 1, j - 1);\n        return memo[i][j] = 1 + Math.min(go(s, i + 1, j), go(s, i, j - 1));\n    };\n    return go(s, 0, s.length - 1);\n};\n```\n\n*Javascript: with memo (refactored with a few less lines of code)*\n```\nlet minInsertions = (s, m = [...Array(501)].map(x => Array(501).fill(-1))) => {\n    let go = (s, i, j) => {\n        return m[i][j] =\n            m[i][j] > -1 ? m[i][j] :\n            i >= j ? 0 :\n            s[i] == s[j] ? go(s, i + 1, j - 1) :\n            1 + Math.min(go(s, i + 1, j), go(s, i, j - 1));\n    };\n    return go(s, 0, s.length - 1);\n};\n```\n\n**Javascript Solutions: DP Bottom-Up**\n\n*Javascript: full DP matrix (non-optimized for memory)*\n```\nlet minInsertions = (s, dp = [...Array(501)].map(x => Array(501).fill(0))) => {\n    let N = s.length;\n    for (let i = N - 1; i >= 0; --i)\n        for (let j = i + 1; j <= N; ++j)\n            if (s[i] == s[j - 1])\n                dp[i][j] = dp[i + 1][j - 1];\n            else\n                dp[i][j] = 1 + Math.min(dp[i + 1][j], dp[i][j - 1]);\n    return dp[0][N];\n};\n```\n\n*Javascript: pre/cur row (optimized for memory)*\n```\nlet minInsertions = (s, pre = [...Array(501)].fill(0), cur = [...Array(501)].fill(0)) => {\n    let N = s.length;\n    for (let i = N - 1; i >= 0; --i, [pre, cur] = [cur, pre])\n        for (let j = i + 1; j <= N; ++j)\n            if (s[i] == s[j - 1])\n                cur[j] = pre[j - 1];\n            else\n                cur[j] = 1 + Math.min(pre[j], cur[j - 1]);\n    return pre[N];\n};\n```\n\n*Javascript: pre/cur row (optimized for memory + more concise code)*\n```\nlet minInsertions = (s, pre = [...Array(501)].fill(0), cur = [...Array(501)].fill(0)) => {\n    let N = s.length;\n    for (let i = N - 1; i >= 0; --i, [pre, cur] = [cur, pre])\n        for (let j = i + 1; j <= N; ++j)\n                cur[j] = s[i] == s[j - 1] ? pre[j - 1] : 1 + Math.min(pre[j], cur[j - 1]);\n    return pre[N];\n};\n```\n\n**C++ Solutions: Recursive Top-Down**\n\n*C++: TLE without memo*\n```\nclass Solution {\npublic:\n    int minInsertions(string s) {\n        int n = s.size();\n        return go(s, 0, n - 1);\n    }\nprivate:\n    int go(const string& s, int i, int j) {\n        if (i >= j)\n            return 0;\n        if (s[i] == s[j])\n            return go(s, i + 1, j - 1);\n        return 1 + min(go(s, i + 1, j), go(s, i, j - 1));\n    }\n};\n```\n\n*C++: with memo*\n```\nclass Solution {\npublic:\n    int minInsertions(string s) {\n        int n = s.size();\n        return go(s, 0, n - 1);\n    }\nprivate:\n    using VI = vector<int>;\n    using VVI = vector<VI>;\n    VVI memo = VVI(501, VI(501, -1));\n    int go(const string& s, int i, int j) {\n        if (memo[i][j] > -1)\n            return memo[i][j];\n        if (i >= j)\n            return memo[i][j] = 0;\n        if (s[i] == s[j])\n            return memo[i][j] = go(s, i + 1, j - 1);\n        return memo[i][j] = 1 + min(go(s, i + 1, j), go(s, i, j - 1));\n    }\n};\n```\n\n*C++: with memo (refactored with a few less lines of code)*\n```\nclass Solution {\npublic:\n    int minInsertions(string s) {\n        int n = s.size();\n        return go(s, 0, n - 1);\n    }\nprivate:\n    using VI = vector<int>;\n    using VVI = vector<VI>;\n    VVI m = VVI(501, VI(501, -1));\n    int go(const string& s, int i, int j) {\n        return m[i][j] =\n            m[i][j] > -1 ? m[i][j] :\n            i >= j ? 0 :\n            s[i] == s[j] ? go(s, i + 1, j - 1) :\n            1 + min(go(s, i + 1, j), go(s, i, j - 1));\n    }\n};\n```\n\n**C++ Solutions: DP Bottom-Up**\n\n*C++: full DP matrix (non-optimized for memory)*\n```\nclass Solution {\npublic:\n    using VI = vector<int>;\n    using VVI = vector<VI>;\n    int minInsertions(string s, VVI dp = VVI(501, VI(501))) {\n        int N = s.size();\n        for (auto i = N - 1; i >= 0; --i)\n            for (auto j = i + 1; j <= N; ++j)\n                if (s[i] == s[j - 1])\n                    dp[i][j] = dp[i + 1][j - 1];\n                else\n                    dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j - 1]);\n        return dp[0][N];\n    }\n};\n```\n\n*C++: pre/cur row (optimized for memory)*\n```\nclass Solution {\npublic:\n    using VI = vector<int>;\n    int minInsertions(string s, VI pre = VI(501), VI cur = VI(501)) {\n        int N = s.size();\n        for (auto i = N - 1; i >= 0; --i, swap(pre, cur))\n            for (auto j = i + 1; j <= N; ++j)\n                if (s[i] == s[j - 1])\n                    cur[j] = pre[j - 1];\n                else\n                    cur[j] = 1 + min(pre[j], cur[j - 1]);\n        return pre[N];\n    }\n};\n```\n\n*C++: pre/cur row (optimized for memory + more concise code)*\n```\nclass Solution {\npublic:\n    using VI = vector<int>;\n    int minInsertions(string s, VI pre = VI(501), VI cur = VI(501)) {\n        int N = s.size();\n        for (auto i = N - 1; i >= 0; --i, swap(pre, cur))\n            for (auto j = i + 1; j <= N; ++j)\n                cur[j] = s[i] == s[j - 1] ? pre[j - 1] : 1 + min(pre[j], cur[j - 1]);\n        return pre[N];\n    }\n};\n```
[]