We generally use [n1][n2] memory to calculate the LCS length of two strings having length n1 and n2. Can it be calculated in [2][max(n1,n2)]? Can any one explain it clearly?
We generally use [n1][n2] memory to calculate the LCS length of two strings having length n1 and n2. Can it be calculated in [2][max(n1,n2)]? Can any one explain it clearly?
Not only it can be calculated using a matrix, it can also be calculated using a matrix (or even a vector). See here.
If you're looking for a "general" explanation of how you can use less memory in some DP tasks, then have a look at this.
Thank you. :)