traceback
Walking back through a filled dynamic-programming table from the final cell to recover the choices that produced the optimal answer.
In more detail
At each cell you ask which neighbouring cell its value came from, step there, and record the choice. For LCS, a diagonal step means the characters matched and belong to the subsequence. In Python, "traceback" also names the error report printed for an uncaught exception.
Related terms
- tabulation — Bottom-up dynamic programming: filling a table of subproblem answers in order from the base cases up, so each entry's inputs are ready before it.
- longest common subsequence — The longest sequence of characters that appears, in order but not necessarily side by side, in both of two strings.
- knapsack problem — The problem of choosing items, each with a weight and a value, to maximise total value without exceeding a weight capacity.
Taught in
- Counting And Radix Sort: Beating N Log N — Algorithms & Data Structures for Working Engineers
- Dynamic Programming: Memoisation And Tabulation — Algorithms & Data Structures for Working Engineers