DP - 9: Longest Palindrome Subsequence

Source Code:https://thecodingsimplified.com/longe...
Solution - 1: Recursive Basic Solution
We start from start = 0 & end = length - 1
If values at start & end indexes are equal then recursively check for remaining start + 1 & end - 1 & add 2
It's not matching, then Get the maximum of lps(start, end - 1), lcs(start + 1, end)

Time Complexity: O(2^n)
Space Complexity: O(n)

Solution - 2: Top Down DP Solution
We start from start = 0 & end = length - 1 & initialize a 2D array
If values at start & end indexes are equal then recursively check for remaining start + 1 & end - 1 & add 2
It's not matching, then Get the maximum of lps(start, end - 1), lcs(start + 1, end)
At every position we check, if value is null means we need to find the value, if it's not null then value
exists in array & return from array.

Time Complexity: O(n * n)
Space Complexity: O(n * n)

Solution - 2: Bottom UP DP Solution
We initialize 2D array & represent string in 2D form
We start 1 loop starting from 2nd last row (i) & another loop from j = i + 1, which'll check every combination
If value matches, then 2 + arr[start + 1][end - 1]
If not matching, then Max(arr[start][end-1], arr[start+1][end])
at last we return arr[0][n-1]

Time Complexity: O(n * n)
Space Complexity: O(n * n)

Do Watch video for more info

CHECK OUT CODING SIMPLIFIED
   / codingsimplified  

★☆★ VIEW THE BLOG POST: ★☆★
http://thecodingsimplified.com

I started my YouTube channel, Coding Simplified, during Dec of 2015.
Since then, I've published over 400+ videos.

★☆★ SUBSCRIBE TO ME ON YOUTUBE: ★☆★
   / codingsimplif.  .

★☆★ Send us mail at: ★☆★
Email: [email protected]