Longest Common Subsequence: 3 Detailed Solutions (Recursion, Memoization, Dynamic Programming)

I talk about a common dynamic programming problem called the longest common subsequence (LCS). I provide a few detailed solutions ranging from generating all of the possible subsequences of each given sequence to using dynamic programming to solving the problem:

1. Brute force solution by generating all possible subsequences O(2^n) time 1:38 - 9:25 [Note, I said that this approach takes O(n) because of the recursion depth; however, the seen variable actually holds all of the subsequences. Thus, the space complexity should be O(2^n) as well.
2. Brute force solution with recursion O(2^n) time 4:40 - 18:50
3. Recursive solution with caching solved states O(n * m) time 18:50 - 29:45
4. Iterative solution O(n * m) time 29:45 - 46:00

Feel free to ask any questions!

Comment below for what question I should solve next, if there is a mistake in the video or if you want to share your approach!