TRT
Sign in

Advanced · Module 15 · Lesson 6 of 6

Rebuilding the answer and saving memory

A DP table holds the value of the best solution, not the solution itself. Walking back through the table recovers the choices. When only the value is needed, keeping one or two rows cuts memory from O(n × m) to O(m).

Pro — members onlyAbout 14 minutes

By the end you can

  • Reconstruct an optimal solution by retracing the decisions recorded in a DP table
  • Reduce memory to one or two rows, or a few variables, when each row depends only on the previous one
  • Explain the tension between saving memory and reconstructing, and how divide and conquer resolves it

Builds on Knapsack and subsets.

01 · A question first

An edit-distance table for two 100,000-character files has ten billion cells: 40 GB of integers. The distance itself needs only two rows, 800 KB. What do you lose when you throw the rest of the table away, and how do diff tools get the actual edits back anyway?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • The value is not the solution
  • Walking back
  • Keeping only what the recurrence reads
  • Having both: Hirschberg's algorithm
  • Memory in practice
  • Choosing
  • Pseudocode & Multi-Language Implementations (C++, Java, Python)
  • Complexity Derivation, Edge Cases & Common Mistakes
See plansAlready a member? Sign in

03 · Practice

Practice · medium · LeetCodeEdit distanceFind the fewest insertions, deletions and replacements to turn one word into another, with a table over prefixes, then in two rows.Practice · hard · LeetCodeShortest common supersequenceBuild the shortest string containing both inputs as subsequences by walking back through an LCS table.

Asked in interviews

Something wrong with this lesson? Report a problem