human
Longest Palindromic Subsequence | DP | Returns the length of the longest palindromic subsequence in seq.
Create a table to store results of subproblems.
Strings of length 1 are palindrome of length 1.
Build the table . Note that the lower diagonal values of table are useless and not filled in the process . The values are filled in a manner similar to Matrix Chain Multiplication DP solution ( See https : www . geeksforgeeks . org / dynamic - programming - set - 8 - matrix - chain - multiplication / cl is length of substring.
Driver program to test above functions"
How can the above be solved in Python?
assistant
#Here is code to longest Palindromic Subsequence and the other steps required.
 def lps ( str ) :
	n = len ( str )
	L = [ [ 0 for x in range ( n ) ] for x in range ( n ) ]
	for i in range ( n ) :
		L [ i ] [ i ] = 1
	for cl in range ( 2 , n + 1 ) :
		for i in range ( n - cl + 1 ) :
			j = i + cl - 1
			if str [ i ] == str [ j ] and cl == 2 :
				L [ i ] [ j ] = 2
			elif str [ i ] == str [ j ] :
				L [ i ] [ j ] = L [ i + 1 ] [ j - 1 ] + 2
			else :
				L [ i ] [ j ] = max ( L [ i ] [ j - 1 ] , L [ i + 1 ] [ j ] ) ;
	return L [ 0 ] [ n - 1 ]
seq = " GEEKS ▁ FOR ▁ GEEKS "
n = len ( seq )
print ( " The ▁ length ▁ of ▁ the ▁ LPS ▁ is ▁ " + str ( lps ( seq ) ) )