Longest Palindrome Subsequence - Solution Using DP

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 tree just to confirm that the subproblems are overlapping.