Python Simple Recursive DP with Explanation
Define dp(s) as the minimum number of steps to make s palindrome.\nWe\'ll get the recursion below:\ndp(s) = 0 if s == s[::-1]\ndp(s) = dp(s[1:-1]) if s[0] == s[
Define `dp(s)` as the minimum number of steps to make `s` palindrome.\nWe\'ll get the recursion below:\n`dp(s) = 0 if s == s[::-1]`\n`dp(s) = dp(s[1:-1]) if s[0] == s[-1]`\n`dp(s) = 1 + min(dp(s[1:]), dp(s[:-1])) otherwise`\n\n\n```python\nfrom functools import lru_cache\n\n\nclass Solution:\n    def minInsertions(self, s: str) -> int:\n        @lru_cache(None)\n        def dp(s):\n            if s == s[::-1]:\n                return 0\n            elif s[0] == s[-1]:\n                return dp(s[1:-1])\n\t\t\telse:\n\t\t\t\treturn 1 + min(dp(s[1:]), dp(s[:-1]))\n        \n        return dp(s)\n```
['Dynamic Programming', 'Recursion', 'Python', 'Python3']