Dynamic programming is often introduced as a way to find a maximum or minimum. That description is useful, but incomplete: dynamic programming really solves optimization problems, where we choose one optimal feasible solution from many possibilities.
Optimal solutions versus objective values
Consider the House Robber problem. The original problem asks for the highest amount that can be stolen without robbing adjacent houses. A related variant asks for the actual set of houses that achieves that amount. The latter is the optimal solution, while the former is only its value.
Knowing the optimal solution gives us its value for free, but knowing the value does not tell us which choices produced it. Fortunately, we can reconstruct the choices without changing the original time and space complexity.
Example 1: House Robber
Suppose dp[k] stores the maximum amount obtainable from the first k houses. The recurrence is:
The value in dp[k] comes either from dp[k-1] or from dp[k-2] plus the current house. We can record that choice in a back array instead of copying the entire solution into every DP cell:
int[] dp = new int[N + 1];
int[] back = new int[N + 1];
dp[0] = 0;
dp[1] = nums[0];
back[1] = -2;
for (int k = 2; k <= N; k++) {
if (dp[k - 1] >= dp[k - 2] + nums[k - 1]) {
dp[k] = dp[k - 1];
back[k] = -1;
} else {
dp[k] = dp[k - 2] + nums[k - 1];
back[k] = -2;
}
}Starting at dp[N], follow back toward the beginning. A -2 step means that house k - 1 belongs to the solution; a -1 step means it does not. Reverse the collected indices at the end.
For a refresher on the original recurrence, see House Robber: Four Steps for Solving Dynamic Programming Problems.
Example 2: Longest Common Subsequence
The same idea works for a two-dimensional DP table. Let dp[i][j] be the length of the longest common subsequence of s[0..i) and t[0..j). Each cell comes from the upper-left, upper, or left cell. Store that direction in back[i][j].
When walking backward from dp[m][n], a diagonal step records a matching character, an upward step decrements i, and a leftward step decrements j. Reversing the recorded characters yields the actual longest common subsequence rather than only its length.
Review the two-dimensional recurrence in Longest Common Subsequence: The Two-Dimensional Dynamic Programming Solution.
A general method for recovering optimal solutions
For any dynamic programming problem:
- Define the subproblem.
- Write its recurrence.
- Determine the computation order.
- Compute the DP and back arrays together.
- Start from the final subproblem and follow the back array to reconstruct the choices.
The extra back array preserves the information needed for reconstruction. Space optimization can remove that information, so it should be applied only when the concrete solution is not needed.