This post is completed by 2 users

Add to List 
Dynamic Programming — Longest Palindromic Subsequence
Objective: Given a string, find a longest palindromic subsequence in it.
What is Longest Palindromic Subsequence: A longest palindromic subsequence is a sequence that appears in the same relative order, but not necessarily contiguous(not substring) and palindrome in nature( means the subsequence will read same from the front and back.
Example: String A = " AABCDEBAZ"; Longest Palindromic subsequence: ABCBA or ABDBA or ABEBA There are many subsequences can be found which are palindrome like, AA, BCB, ABA, BB etc but we need to find the one with the maximum length.
Approach:
Recursion:
Check every subsequence of in a given string, which means every character as two options, whether it will be included in the subsequence or it will be excluded. If we do it by recursion which means all the sub problems will be solved repeatedly that means Time Complexity will be O(2^{n}).
We can do it better by solving this problem using Dynamic Programming.
Dynamic Programming:
Optimal Substructure:
Given Sequence A[0….n1]
LPS[0….n1] be the longest palindromic subsequence of the given sequence.
Check the first and the last characters of the sequence. Now there are two possibilities, either both the characters same or distinct. We will have to handle both the case.
 If both characters are same, add 2 to the result and remove both the characters and solve the problem for the remaining subsequence .
 If both characters are different, then solve the problem twice, ignore the first character (keep the last character)and solve the remaining subsequence and then ignore the last character (keep the first character) and solve it and pick the best out of two results.
Overlapping Subproblems:
Say given input string: ABCDE
If we solve it recursively, look at the recursion tree, we will be solving the subproblems repeatedly.
So while using the dynamic programming, we will solve it in bottomup manner and store the results of subproblems once we solve them for future reference. See the code for the better explanation
Recursive Equations:
LPS[i, i]  =  1  Every single character is a palindrome by itself of length 1 
LPS[i, j]  =  2  if j=i+1, sequence has only 2 characters 
LPS[i, j]  =  2 + LPS[i1, j1]  If first and last characters are same 
LPS[i, j]  =  MAX(LPS[i+1,j], LPS[i, j1])  If first and last characters are not same 
Code:
Output:
Output:
1 2 2 2 2 2 3 5 5 0 1 1 1 1 1 3 5 5 0 0 1 1 1 1 3 3 3 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1
Also Read: