Another problem where dynamic programming is applicable is in the comparison of sequences. Given two sequences A and B, what is the miniml number of operations to turn A into B? The allowable operations are: insert a new symbol, delete a symbol, and replace a symbol. Each operation costs one unit.
A program to do this is:
/* sequence comparisons. How to change one sequence into another. A=a_1 a_2 ... a_n B=b_1 b_2 b_3 ... b_m Change A into B using 3 operations: insert, delete, replace: each operation costs 1. */ % c(N,M,C) if C is minimum cost of changing a_1...a_N into b_1...b_M :- table c/3. c(0,0,0). c(0,M,M) :- M > 0. % must insert M items c(N,0,N) :- N > 0. % must delete N items c(N,M,C) :- N > 0, M > 0, N1 is N-1, M1 is M-1, c(N1,M,C1), C1a is C1+1, % insert into A c(N,M1,C2), C2a is C2+1, % delete from B c(N1,M1,C3), % replace a(N,A), b(M,B), (A==B -> C3a=C3; C3a is C3+1), min(C1a,C2a,Cm1), min(Cm1,C3a,C). % take best of 3 ways min(X,Y,Z) :- X =< Y -> Z=X ; Z=Y. % example data a(1,a). a(2,b). a(3,b). a(4,c). a(5,b). a(6,a). a(7,b). b(1,b). b(2,a). b(3,b). b(4,b). b(5,a). b(6,b). b(7,b).The first three clauses for
c/3
are clear; most of the work is
done in the last clause. It reduces the problem to a smaller problem
in three different ways, one for each of the operations of insert,
delete, and replace. Each reduction costs one unit, except that
``replacement'' of a symbol by itself costs nothing. It then takes
the minimum of the costs of these ways of turning string A into string
B.
In Prolog this would be exponential. With tabling it is polynomial.