Reconstructing Optimal DP Solutions

After computing optimal value, walk back parents or argmin choices to print the path, partition, or assignment.

Why this shows up in the real world

Diff tools reconstruct LCS. Project selection prints chosen items.

Core idea (explained for students)

Store choice[i] during fill, or recompute greedy from end using stored dp values.

Try this in Python

def lcs_reconstruct(a: str, b: str) -> str:
    na, nb = len(a), len(b)
    dp = [[0] * (nb + 1) for _ in range(na + 1)]
    for i in range(1, na + 1):
        for j in range(1, nb + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    i, j = na, nb
    out = []
    while i and j:
        if a[i - 1] == b[j - 1]:
            out.append(a[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(out))


print(lcs_reconstruct('abcde', 'ace'))

Common mistakes

• Multiple optimal solutions—tie-break rules unstated.
• Parent table not updated when optimizing space.

Key takeaways

• Snapshot decisions in an array parallel to dp.