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)