Dynamic programming is a way of solving problems that uses a table. Answers to subproblems are stored in the table instead of, as recursion does, recomputing them. I used a technique called Memoization where recursion is used but the results are stored in a table and if we need a result that has been calculated it is just looked up in the table and then returned, instead of recomputing the result.

The problem I am looking at is a version of a problem called the Edit Distance problem. In it we change one word to another by using certain operations. In this version we use copy, replace, insert, delete and kill. Each operation has a cost associated to it and we are looking for the set of operations that has the lowest cost. We are given the the two words X and Y. We assume there is an array Z that is initially empty. The operations place the characters in Z until Z is the same as Y. We let i and j be the indices into X and Z respectively. In the table I store which operation is used to change the the letter from X[i] to Y[j] assuming the change is for the rest of the words beginning at X[i] and Y[j]. For example if we were using total and other and i is 1 and j is 2 then we select the operation to change o to h assuming that the rest of the the two words is otal and her with 0 being t and o for both of the words. So if the operation chosen is replace I would store that, the letter that it was changed to, and the cost to change the rest of the word in the array location [1,2]. To get the beginning of the solution I look in array position [0,0] and it has the cost to change from X to Y. Then I increase i and j as according to the instructions below and look in position [i,j]. So if it had been a replace in position [0,0] I would then look in position [1,1] since both i and j are incremented with a replace operation. I continue tracing the solution in this way until we reach the end.

Copy This copies a character from X[i] to Z[j] and then increments i and j.

Replace This  replaces a character of X by a character c. So Z[j] is set to c. Then i and j are
               both incremented.

Delete  This deletes a character of X by incrementing i but leaving  Z and j alone.

Insert  This inserts a character c to Z[j] j is incremented but i is not.

Kill   This gets rid of all the remaining letters of X. It must be the last operation.

Enter the costs below. They have to be positive and less than 10.

Operation                   Cost                                                                                                   
 Copy                                                                 
 Replace                                                            
 Delete                                                               
 Insert                                                              
 Kill                                                                  

                                  
                          Enter the beginning and ending words.
                         
                          Beginning                                         
                          Ending             


                         Operations