Dynamic Programming (Additional Notes)

Minimum Edit Distance

Given a string X of length m, and a string Y of length n, where X_i is
the substring of X from positions 1 to i, and X[i] is the i-th letter
of X, then we compute the minimum edit distance array d such that
d[i][j] = MED(X_i,Y_j)

Picture the two-dimensional array d with the characters of X indexed
along the x-axis and the characters of Y indexed along the y-axis,
with an extra row and column for the nul strings, then compute the
following:

for i=0 to m
  for j=0 to n
    d[i][j] = | j<1, i
	      | i<1, j
	      | X[i]==Y[j], d[i-1][j-1]
	      | X[i]!=Y[j], min(d[i-1][j-1]+2,d[i-1][j]+1,d[i][j-1]+1)

If j is zero then we must delete all i characters from X, and if i is
zero then we must add all characters from Y.  If both X and Y are
non-null then it costs nothing to change the i-th character of X into
the j-th character of Y because they are already the same so they may
as well be considered as part of the LCS.  Otherwise we must delete
the i-th character from X and insert the j-th character of Y at a cost
of two added to the already calculated cost of editting X_i-1 into
Y_j-1, or we must delete the i-th character of X at a cost of one to
the already calculated cost of editting X_i-1 into Y_j, or we must
insert the j-th character of Y at a cost of one to already calculated
cost of editting X_i into Y_j-1; whichever of these three options is
the cheapest.


Knapsack Problem

Given N different types of items, numbered from 1 to N, where the size
and value of the i-th item is given in size[i] and value[i]
respectively, we maximize the total haul in a knapsack of capacity M
by computing the maximum haul in knapsacks from size 1 to M.  To
calculate the maximum haul for a knapsack of a given size with N
different items, we compute the maximum haul for that knapsack given 1
to N different types of items.

Assume there is only one type of item, then to calculate the maximum
haul for knapsacks with volume 1 to N we simply see how many items we
can fit in the knapsack and sum their value.  If there are two types
of items, then we see if the total haul of adding this item to the
value of a knapsack whose volume is smaller than the present volume by
exactly the size of the item being considered is greater than the best
haul we have already calculated for a knapsack of the present volume,
and if it is then we add the item to the knapsack.  We always keep
track of the last item we added for a knapsack of a given volume.  In
this way we can list the items we should add to a knapsack of size M
by first listing the best item to add to a knapsack of volume M and
then listing all of the best items added to a knapsack of volume
M-(size of the best item to add to a knapsack of volume M)

for item=1 to N
  for vol=0 to M
    if vol>=size[item]
      if(h[vol-size[item]][item]+value[item] > h[vol][item]
        then 
	     h[vol][item]=h[vol-size[item]][item]+value[item]
	     best2add[vol]=item