I am trying to implement the longest common subsequence algorithm (LCS) in Java. I have been following the above-mentioned tutorial, but I am having trouble understanding how to use the dynamic programming approach.
Can anyone help me understand how to implement the LCS algorithm in Java using dynamic programming?
Thanks in advance for your help!
How comfortable are you with dynamic programming in general? I think this is one of the ones where it’s great to get a lot of foundational practice + theory early on in order to visualize what is happening better. Meaning, start with simple problems, work on them with solid methodology (something like SRTBOT), and finally look at this problem from that angle.
I think for me the biggest a-ha for dynamic programming (beyond simple problems) was conceptualizing the problem-space as a something that needed to be traversed in topographical order (related problems on leetcode: course schedules I and II, topographical sort, detect cycle in a graph). I think before this I used to kind of set up the steps bottom-up/top-down and I knew it had to trickle down to a base-case, but the distinction that it was a topographical ordering made this even clearer as to what it should NOT do.
Less rigorous but maybe useful for this particular problem: https://www.youtube.com/watch?v=ASoaQq66foQ&t=416s
I still advocate for sitting down with some of the MIT material and using their practice problems, or using CLRS or some such reference to build up from examples.