State Compression and Space Optimization

State compression keeps only values that future transitions still need. It changes storage, not the mathematical recurrence. Using LCS, we retain a previous row and a current row instead of an entire prefix-pair table. The lesson also explains in-place update hazards and why a memory optimization that preserves an optimum value may discard direct reconstruction information.

Prerequisites: LCS; 0/1 and Unbounded Knapsack; dependency invariants.

Build the idea

1. Recognize the repeated subproblems

   An O(nm) DP table may be too large even when O(nm) time is acceptable. Inspect the dependency graph: if row i reads only row i−1 and already-computed current-row entries, old rows can be discarded. This is a lifetime argument. Compressing before defining states and dependencies often hides an accidental reuse bug rather than solving memory usage.

2. Define the state

   previous[j] represents LCS length for the completed source prefix i−1 and target prefix j. current[j] represents the new prefix i while being built. We swap input strings if necessary so the target column dimension is smaller; LCS length is symmetric. The two arrays still encode conceptually two-dimensional states, not a new one-parameter problem.

3. Derive the transition

   For equal characters, current[j]=previous[j−1]+1. Otherwise current[j]=max(previous[j], current[j−1]). The left predecessor belongs to the current row; above and diagonal belong to the previous row. After the row is complete, swap vectors in O(1). Old current values need not be cleared if every used cell is overwritten and current[0] is reset.

   $$\mathrm{current}\left[j\right]=\max \left(\mathrm{previous}\right[j],\mathrm{current}[j-1\left]\right)\mathrm{on}\mathrm{mismatch}$$

4. Base cases and computation order

   Both empty-prefix rows initially contain zeros. For each new source character, set current[0]=0 and scan j upward. Reading current[j−1] requires that direction. A single-vector implementation would additionally preserve the old diagonal in a scalar before overwriting. In knapsack, the relevant dependency layers instead determine backward 0/1 versus forward unbounded capacity iteration.

5. Correctness and invariant

   Before processing column j, the previous row is intact and the new row’s columns below j are correct. The original LCS recurrence therefore sees exactly its intended inputs. Swapping establishes the invariant for the next row. Only the length survives:parents/equality comparisons in arbitrarily old rows are gone. Recovering an LCS now needs stored decisions, recomputation or a specialized divide-and-conquer reconstruction method.

6. Work the example

   For a=abc, b=ac, the rows of lengths are [0,0,0] initially, then [0,1,1],[0,1,1],[0,1,2]. At the last c match, previous[1]=1 becomes current[2]=2. The sample abcde/ace returns length 3, but intentionally prints no witness. The table shows conceptual rows even though only two coexist in memory.

   source prefix	previous/current row values
   empty	0,0,0
   a	0,1,1
   ab	0,1,1
   abc	0,1,2

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
int main(){
    std::string a,b;
    std::getline(std::cin,a);
    std::getline(std::cin,b);
    if(b.size()>a.size()){
        std::swap(a,b);
    }
    std::vector<int>previous(b.size()+1),current(b.size()+1);
    for(int i=1;i<=(int)a.size();++i){
        current[0]=0;
        for(int j=1;j<=(int)b.size();++j){
            current[j]=a[i-1]==b[j-1]?previous[j-1]+1:std::max(previous[j],current[j-1]);
        }
        std::swap(previous,current);
    } // Previous row and current left cell must remain distinguishable.
    std::cout<<previous.back()<<'\n';
}

Complexity analysis

O(nm) conceptual states and constant transitions give unchanged O(nm) time. O(min(n, m)) DP memory plus O(n+m) stored input strings. No O(nm) reconstruction table is retained. Compression reduces space, not automatically transition count.

Example input and output

Read two lowercase-letter lines, each length 0..5000. Print LCS length only. Columns use the shorter string.

Input

abcde
ace

Output

3

For a=abc, b=ac, the rows of lengths are [0,0,0] initially, then [0,1,1],[0,1,1],[0,1,2]. At the last c match, previous[1]=1 becomes current[2]=2. The sample abcde/ace returns length 3, but intentionally prints no witness. The table shows conceptual rows even though only two coexist in memory.

Practical applications

Use rolling arrays for layered DP with bounded dependency lifetime. 0/1 knapsack and unbounded knapsack can compress to one row under different directions. Bitmask state compression is a different idea:it encodes subsets rather than reusing storage lifetimes.

Check your understanding

What must be known before discarding a DP row?

Put it into practice

Compare full-table and rolling-row LCS lengths on empty/repeated-letter strings.