Dynamic Programming Questions Medium
The time complexity of the Dynamic Programming approach for solving the Longest Palindromic Subsequence problem is O(n^2), where n is the length of the input string.
In the Dynamic Programming approach, we use a 2D array to store the lengths of the longest palindromic subsequences for different substrings of the input string. We start by initializing the diagonal elements of the array with 1, as each individual character is a palindrome of length 1.
Then, we iterate through the array diagonally, filling in the values based on the following conditions:
- If the characters at the current positions are the same, we increment the length of the longest palindromic subsequence by 2 and move diagonally to the next position.
- If the characters at the current positions are different, we take the maximum of the lengths obtained by moving either horizontally or vertically in the array.
Since we need to fill in each cell of the 2D array once, the time complexity of this approach is O(n^2).