Q:

Dynamic Programming - How to get the solution from the predecessor matrix

Whenever I'm coding a dynamic program , I usually struggle building the solution from the predecessor matrix . How should use the predecessor matrix to find the solution ?
Thanks,

A:

That depends a lot on the question, really. But basically, since you have the values of the all your "sub-problems", and you know your formula for the problem (Meaning, how the current problem is solved using the optimized solutions for the smaller problem), you can just check which cells (That are possible optimized solutions) in the matrix satisfy this formula.
Then, you can know that this cell is part of the solution.
Continue this way from top to bottom - and you'll get your whole solution (And not just the value, which is I guess was your problem).

