# Tracking Solution with Multiple Matrices in Dynamic Programming

We recently figured out a Dynamic Programming solution to compare two trees using concepts of edit distance in strings. It goes something like this-

$A[i', i, j', j] = \min \begin{cases} B[i', i-1, j', j] + c(i) \\ \min_{j_1 \le k \le j} \{A[i', p(i), j_1, k] + B[p(i) +1, i-1, k+1, j] + d \} \end{cases}$

$B[i', i, j', j] = min\begin{cases} B[i', i-1, j', j-1] + c(i,j) \\ A[i', i, j', j] \end{cases}$

We start at $B[0, 0, 0, 0]$ and finally obtain the answer at $B[0, n, 0, n]$

My question is how do we trace back the solution? This is the first time I see an addition of two different matrices while finding a minimum (see the second condition in A). Is there a standard way of tracing back for such algorithms?

• It's the same as in the case of one matrix. Whenever you have a minimum of several things, you have to record which of them was the minimum. – Yuval Filmus Jul 3 '17 at 11:05
• Yes, you are right - How do I record which one was minimum when I am adding them? – user2785161 Jul 3 '17 at 11:06
• Be creative. Use your programming skills. Imagine you'd have to program it - what would you do? – Yuval Filmus Jul 3 '17 at 11:13
• Dear, I am programming it. Stuck for a week. – user2785161 Jul 3 '17 at 11:20
• When taking the minimum of a set, you need to store the expression which achieves the minimum. From here it's just a programming exercise. – Yuval Filmus Jul 3 '17 at 13:42