Printing the path traversed in a dynamic programming solution

Question

The question is simple: in a typical dynamic programming solution, how can one print the actual states that were traversed during computation of the final solution?

Let me try to explain with the help of an example what exactly I need-

Suppose, we have a DP solution to a problem where each state will have two-dimensions i.e. a state in the solution will look like (i,j). Now, we have a starting state (0,0) and some final states: (i,n), where i varies from 0 to n.

So, a typical solution will work like this:

Start from a starting state: in this case -> (0,0)
Move to the next state based on some computation: suppose from (0,0), we could go to (1,0), (1,1) or (1,2).
.
.
Keep on traversing until we reach one of the end states: in this case (i,n), for any i.

Now, I need to print the path traversed in this solution. Basically, if I can find out from which state I reached the final state, I can use that logic to go back upto the starting state and consequently print the path.

P.S.: Apologies if the question seems too obvious.

Answer 1

1. You can store this information explicitly during the computations. That is, besides DP(i, j), you can save PARENT(i, j), which represents a state which we came from to obtain the result for (i, j)(and update it properly when you make transitions during the initial computations).

2. Sometimes, we can compute PARENT(i, j) without storing it explicitly. It is the case when:

   • It is possible to figure out from which states we could make transitions to the current one.

   • We can check whether a transition is the one that gave us an optimal solution for this state.

When we know the parent of each state, we can just start iterating from the final state, adding each state to a list and then proceeding to its parent until we reach the start state(and reversing the list in the end if necessary). We can also do the same thing recursively.

Here is a(maybe trivial) example:

Let's assume that we are solving a standard problem: given a grid with numbers on it, find the path from the left-top corner to the right-bottom corner with maximum sum if we are allowed to move only right or down.

Computing parent explicitly(I omit corner cases here):

if dp(i - 1, j) > dp(i, j - 1) then
    dp(i, j) = a(i, j) + dp(i - 1, j)
    par(i, j) = (i - 1, j)
else
    dp(i, j) = a(i, j) + dp(i, j - 1)
    par(i, j) = (i, j - 1)

Implicitly:

let getPar(i, j)
    if dp(i - 1, j) > dp(i, j - 1)
        return (i - 1, j)
    return (i, j - 1)

The idea is the same for more sophisticated problems.