find the length of the longest palindrome subsequence in O(n^2)

longestPalindromeLength.py

#!/usr/bin/python
class LongestPalindrome:
    def longestPalindrome(self, string):
        self.string = string
        self.LP = {}
        return self.longestPalindrome_(0, len(self.string) - 1)

    def longestPalindrome_(self, i, j):
        if (i, j) in self.LP:
            return self.LP[(i, j)]
        elif j == i:
            return 1
        elif j < i:
            return 0
        else:
            if self.string[i] == self.string[j]:
                length = self.longestPalindrome_(i+1, j-1) + 2
            else:
                length = max(self.longestPalindrome_(i+1, j),
                             self.longestPalindrome_(i, j-1))
            if (i, j) not in self.LP:
                self.LP[(i, j)] = length
            return length

f = LongestPalindrome()
assert f.longestPalindrome("12321") == 5
assert f.longestPalindrome("123321") == 6
assert f.longestPalindrome("1233321") == 7
assert f.longestPalindrome("01233321") == 7
assert f.longestPalindrome("12333210") == 7
assert f.longestPalindrome("1203303210") == 8