def dp_palindrome_length(dp, S, i, j):
  """
  Recursive function for finding the length
  of the longest palindromic sequence
  in a string

  This is the algorithm covered in the lecture

  It uses memoization to improve performance,
  dp "dynamic programming" is a Python dict
  containing previously computed values

  """
  if i == j:
    return 1
  if (i, j) in dp:
    return dp[(i, j)]
  if S[i] == S[j]:
    if i + 1 == j:
      dp[(i, j)] = 2
    else:
      dp[(i, j)] = 2 + \
        dp_palindrome_length(dp, S, i + 1, j - 1)
  else:
    dp[(i, j)] = \
      max(
        dp_palindrome_length(dp, S, i + 1, j),
        dp_palindrome_length(dp, S, i, j - 1))
  return dp[(i, j)]