If only the LCS LENGTH is needed (not the actual subsequence string), the DP table can be stored in
AO(min(m, n)) space using two rolling rows
BO(mn²) space because of duplicate paths
CO(1) space because length is just an integer
DO(m + n) space using a stack of indices
Answer & Solution
Correct answer: A. O(min(m, n)) space using two rolling rows
Each cell depends only on the row above and the cell to the left in the current row. So keep two rolling rows; the older one can be discarded once it's been used to compute the newer. O(min(m, n)) space if you orient rows along the shorter string. You can't get O(1) because you do need the current and previous row; reconstructing the actual LCS does need the full table.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for