<p>Given a string <code>s</code>. In one step you can insert any character at any index of the string.</p>

<p>Return <em>the minimum number of steps</em> to make <code>s</code>&nbsp;palindrome.</p>

<p>A&nbsp;<b>Palindrome String</b>&nbsp;is one that reads the same backward as well as forward.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;zzazz&quot;
<strong>Output:</strong> 0
<strong>Explanation:</strong> The string &quot;zzazz&quot; is already palindrome we do not need any insertions.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;mbadm&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> String can be &quot;mbdadbm&quot; or &quot;mdbabdm&quot;.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;leetcode&quot;
<strong>Output:</strong> 5
<strong>Explanation:</strong> Inserting 5 characters the string becomes &quot;leetcodocteel&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 500</code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

# class Solution:
#     def minInsertions(self, s: str) -> int:

#         n = len(s)
#         dp = [[float("inf")] * (n + 1) for _ in range(n + 1)]

#         for i in range(n-1, -1, -1): 
#             for j in range(i, n): 

#                 if s[i] == s[j]: 
#                     if j - i < 2:
#                         dp[i][j] = 0
#                     else: 
#                         dp[i][j] = dp[i + 1][j - 1]
#                 else: 
#                     dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j - 1])
        
#         return dp[0][n - 1]


        # n = len(s)
        # dp = [[0] * n for _ in range(n)]

        # # Fill the dp table
        # for length in range(2, n + 1):
        #     for i in range(n - length + 1):
        #         j = i + length - 1
        #         print(i, j)
        #         if s[i] == s[j]:
        #             dp[i][j] = dp[i + 1][j - 1]
        #         else:
        #             dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j - 1])

        # return dp[0][n - 1]




class Solution:
    def minInsertions(self, s: str) -> int:
        memo = {}

        def dfs(l, r):
            if l >= r:
                return 0

            if (l, r) in memo:
                return memo[(l, r)]

            if s[l] == s[r]:
                memo[(l, r)] = dfs(l + 1, r - 1)
            else:
                memo[(l, r)] = 1 + min(dfs(l + 1, r), dfs(l, r - 1))

            return memo[(l, r)]

        return dfs(0, len(s) - 1)

131270