Multiple Optimal Solutions in Dynamic Programming

In 2-D dynamic programming problems like Edit Distance and binary knapsack, there can be multiple optimal solutions. By tracing back from the last element in the matrix one could trace out all the possible solutions.

Here’s the question: How to count the number of unique optimal solutions without backtracking? Is it even possible?

I’ve been stuck on this problem for a while. Any help would be appreciated.

Example: The edit distance between two strings, TREE and TOR is 3.However, it has four optimal solutions.

1) TREE TOR_

Replace(R,O), Replace(E,R), Delete(E)

2) TREE TO_R

Replace(R,O), Delete(E) Replace(E,R)

3) TREE T_OR

Delete(R), Replace(E,O), Replace(E,R)

4) T_REE TOR__

Insert(O), Delete(E), Delete(E)