Exercises

3.2 Palindromic Edit Distance

Fully solved by ChatGPT DP Problem

Minimum edit distance to make a string A a palindrome.

We use a DP[n][n] table where each entry is: “minimum edit distance to make A[i..j] a palindrome.

BC: All 0 Then the recursion is:

• if A[i] == A[j] we can move in for free DP[i + 1][j - 1]
• else we can either
  • remove left DP[i + 1][j] + 1
  • remove right DP[i][j - 1] + 1
  • edit DP[i + 1][j - 1] + 1