DP - 9: Longest Palindrome Subsequence скачать в хорошем качестве

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: thecodingsimplified@gmail.com