Incremental DP (Localized Table Updates)

Update DP when data streams or a single element changes—sometimes only a band of the table needs refresh (e.g., localized edit distance).

Why this shows up in the real world

Collaborative editors approximate incremental diff scores. Incremental compilation refreshes affected graph slices.

Core idea (explained for students)

Track dirty regions or difference from previous prefix sums; for small edits, recompute O(n) strip not full n^2 sometimes.

Try this in Python

def edit_distance_incremental(a: str, b: str) -> int:
    # standard full recompute (illustrative)
    na, nb = len(a), len(b)
    prev = list(range(nb + 1))
    for i in range(1, na + 1):
        cur = [i] + [0] * nb
        for j in range(1, nb + 1):
            cost = 0 if a[i - 1] == b[j - 1] else 1
            cur[j] = min(prev[j] + 1, cur[j - 1] + 1, prev[j - 1] + cost)
        prev = cur
    return prev[-1]


print(edit_distance_incremental('kitten', 'sitting'))

Common mistakes

• Recomputing entire table on tiny edits—waste.
• Stale caches when multiple edits interleave.

Key takeaways

• Amortize with rolling arrays when only last row matters.