Longest Palindrome Subsequence - Solution Using DP
Understand how to apply dynamic programming to find the longest palindromic subsequence in a string. Learn to convert an exponential recursive approach into an optimized solution by storing intermediate results, reducing computation time and handling overlapping subproblems effectively.
We'll cover the following...
We'll cover the following...
The problem with the previous approach
As we implemented the solution using Recursion in the previous lesson, we got exponential time complexity. By visualizing the recursion tree, we can easily confirm that the subproblems are overlapping, and hence, we can use dynamic programming to solve this problem. Let’s first look at a partial recursion ...