Python easy 7-liner | DP | Top-down & Bottom-up
Code\n\nTop Down\n\nclass Solution:\n    def minInsertions(self, s: str) -> int:\n        @lru_cache(None)\n        def dp(i, j):\n            if i >= j:\n     
# Code\n\n***Top Down***\n```\nclass Solution:\n    def minInsertions(self, s: str) -> int:\n        @lru_cache(None)\n        def dp(i, j):\n            if i >= j:\n                return 0\n\n            if s[i] == s[j]:\n                return dp(i+1, j-1)\n            else:\n                return 1+min(dp(i+1, j), dp(i, j-1))\n\n        return dp(0, len(s)-1)\n```\n\n***Bottom-up***\n```\nclass Solution:\n    def minInsertions(self, s: str) -> int:\n        n = len(s)\n        dp = [[0 for _ in range(n)] for _ in range(2)]\n        i = 0\n        for i in range(n-2, -1, -1):\n            for j in range(i+1, n):\n                if s[i] == s[j]:\n                    dp[i%2][j] = dp[(i+1)%2][j-1]\n                else:\n                    dp[i%2][j] = 1+min(dp[(i+1)%2][j], dp[i%2][j-1])\n\n        return dp[i%2][n-1]\n```\nNote: To reduce space complexity, matrix of 2xn is used here. Same can be achieved using nxn matrix which is easy to interpret.\n\nOR (same as above)\n\n```\nclass Solution:\n    def minInsertions(self, s: str) -> int:\n        n = len(s)\n        dp = [[0 for _ in range(n)] for _ in range(2)]\n        \n        i = 0\n        for i in range(n-2, -1, -1):\n            for j in range(i+1, n):\n                dp[i%2][j] = dp[(i+1)%2][j-1] if s[i] == s[j] else 1+min(dp[(i+1)%2][j], dp[i%2][j-1])\n                \n        return dp[i%2][n-1]\n```\n
['Dynamic Programming', 'Python3']