python 3 - top down dp
Intuition\nLogic is straightforward.\n\nstate variable = left, right\nDo all combination of left and right -> DP should be used.\nIf s[left] == s[right], skip b
# Intuition\nLogic is straightforward.\n\nstate variable = left, right\nDo all combination of left and right -> DP should be used.\nIf s[left] == s[right], skip both left and right. Else, add either s[left] or s[right] and repeat the process.\n\n# Approach\ntop-down dp\n\n# Complexity\n- Time complexity:\nO(n^2) -> dp on all states.\n\n- Space complexity:\nO(n^2) -> cache size\n\n# Code\n```\nclass Solution:\n    def minInsertions(self, s: str) -> int:\n\n        @lru_cache(None)\n        def dp(l, r): # return min step\n            if l >= r:\n                return 0\n            \n            if s[l] == s[r]:\n                return dp(l+1, r-1)\n\n            else: # add left or right\n                t1 = dp(l+1, r) + 1\n                t2 = dp(l, r-1) + 1\n                return min(t1, t2)\n        \n        return dp(0, len(s) - 1)\n```
['Python3']