Longest Palindromic Subsequence - Solution & Explanation

Use a 2D table to keep track of the longest palindromic subsequence. The idea is to fill out this table by solving smaller subproblems and using their results to build up solutions to bigger ones.

The table, dp[i][j], will store the length of the longest palindromic subsequence in s[i...j]. Start by assuming that each character is a palindrome of length 1, and fill the table based on whether the characters at the current indices are the same.

We initialize a 2D table with zero values and then iterate over the string in reverse to ensure that we only use already computed values for dp[i+1][j] and dp[i][j-1] when needed.

This approach defines a recursive function that explores all potential palindromic subsequences, using memoization to store results of overlapping subproblems, thereby avoiding redundant calculations. The function checks if the characters at current indices are equal and proceeds based on that, with memoization avoiding recalculations.

In the recursive approach, a helper function checks the characters from both ends of the string, memoizing already computed results to reduce computational overhead. The "memo" array stores results of already solved subproblems.