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
for cl in range ( 2 , n + 1 ) : NEW_LINE INDENT for i in range ( n - cl + 1 ) : NEW_LINE INDENT j = i + cl - 1 NEW_LINE if str [ i ] == str [ j ] and cl == 2 : NEW_LINE INDENT L [ i ] [ j ] = 2 NEW_LINE DEDENT elif str [ i ] == str [ j ] : NEW_LINE INDENT L [ i ] [ j ] = L [ i + 1 ] [ j - 1 ] + 2 NEW_LINE DEDENT else : NEW_LINE INDENT L [ i ] [ j ] = max ( L [ i ] [ j - 1 ] , L [ i + 1 ] [ j ] ) ; NEW_LINE DEDENT DEDENT DEDENT return L [ 0 ] [ n - 1 ] NEW_LINE