Universal Hirschberg for Width Bounded Dynamic Programs

Logan Nye

Hirschberg's algorithm (1975) reduces the space complexity for the longest common subsequence problem from $O(N^2)$ to $O(N)$ via recursive midpoint bisection on a grid dynamic pro…