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