2. [10 marks In the string metamorphosis problem, you are given two strings 1.m] and y[1.n]. Your task is to determine the least costly way to transform r into y by a left-to-right scan of r while performing operations that affect individual symbols copy, insert, delete and replace. For example, the following is one way of transforming Delicious into Dalhousie Copy the D replace the e with a . copy the l replace the i with h delete the c and i copy the o, u and s insert i ande It is probably best to think of this process as follows: Use an array to store interne- date results. Initially, is empty, and when this process terminates, z = y. We use indices i and j to keep track of the progress that we have made in r and z, respectively. Initially, i = j = 1, and when we finish, we have i = m+ 1,j = n+ 1, During the left-to-write scan of x, . A copy sets x[i] and increments both i and J. A replace sets z[j] c for sonne character c, and increments both i and j . A delete incrementsi only. . An insert sets c for sone character c, and increments J. We assign costs to these operations as follows: A copy is free and it costs nothing, while all the other three operations costs 1 for each single use. Thus, 5 is the cost of transforming Delicious to Dalhousie using the sequence of operations given in the example above. Since no other sequence of operations can transform Delicious to Dalhousie more cheaply, the metamorphosis number of these two strings is 5. Now, use dynamic programming to compute the metamorphosis number of any two given strings