Python. 2 solutions. Recursive 1-liner DP. Iterative space optimised DP.
Approach 1: Recursive DP with memoization\n\n# Complexity\n- Time complexity: O(n^2)\n\n- Space complexity: O(n^2)\n\nwhere, n is length of s.\n\n# Code\nFormat
# Approach 1: Recursive DP with memoization\n\n# Complexity\n- Time complexity: $$O(n^2)$$\n\n- Space complexity: $$O(n^2)$$\n\nwhere, `n is length of s`.\n\n# Code\nFormatted to multiline for readability.\n```python\nclass Solution:\n    def minInsertions(self, s: str) -> int:\n        @cache\n        def min_inserts(i: int, j: int) -> int:\n            return (\n                min_inserts(i + 1, j - 1)\n                if s[i] == s[j]\n                else 1 + min(min_inserts(i, j - 1), min_inserts(i + 1, j))\n            ) if i < j else 0\n        \n        return min_inserts(0, len(s) - 1)\n\n```\n\n---\n\n# Approach 2: Iterative DP with space optimzation\n\n# Complexity\n- Time complexity: $$O(n^2)$$\n\n- Space complexity: $$O(n)$$\n\nwhere, `n is length of s`.\n\n# Code\n```python\nclass Solution:\n    def minInsertions(self, s: str) -> int:\n        n = len(s)\n        dp = [0] * (n + 1)\n        for i in range(n - 1, -1, -1):\n            prev = dp[i]\n            for j in range(i + 1, n):\n                k = j + 1\n                prev, dp[k] = (dp[k], prev if s[i] == s[j] else 1 + min(dp[k - 1], dp[k]))\n        return dp[-1]\n\n\n```
['String', 'Dynamic Programming', 'Recursion', 'Python', 'Python3']