Question

Consider the following problem based on the transformation of a sequence (or collection) of coloured disks Assume that you have a very large collection of disks, each with an integer value representing the disk colour from the range [0, c. For example, the colour mapping might be: O-red, 1-yellow, 2-blue, 3-pink. ..., c-black For a given sequence of coloured disks e.g., ( 0,1,2,3,4 ), at each time step (or iteration) you are only allowed to perform one of three basic operations . remove one disk from the sequence - the disk you select can be any of the disks » insert one disk at any position in the sequence - the disk you select to insert can be any colour in the range 0, c] » replace any single coloured disk in the sequence with a different coloured disk -the replacement disk can be any colour in the range 10. c e.g, (0,1,2,3,4)0,1,2,3,9)

Answer 1

Let us consider two sequences of disks(A,B):
  
m: Length of first sequences of disks
n: Length of second sequences of disks
followings are steps taken two find minimum cost for converting one sequences of disk to another sequences of disk using dynamic programming.

1)Declare an arr[m+1][n+1], which arr[i][j] stores minimum cost of converting sequences of disks A(0,n-1 )into sequences of disks B(0,m-1).
2)for(i=0.......m)
for(j=0.........n)     
    (a)if i=0 If first string is empty, only option is to insert all characters of second string i.e arr[i][j]=n;
    (b)if j=0 If second string is empty, the only option is to remove all characters of first string i.e arr[i][j]=m;
    (c)if last characters of two strings are same, Ignore last characters and recur for remaining strings.
        i.e if(B[i-1]==A[j-1]) arr[i][j]=arr[i-1][j-1];
    (e)if the last character is different, consider all possibilities :-
               (i)   Insert: value for i and j-1 i.e arr[i][j-1]
               (ii) Remove: value for i-1 and j i.e arr[i-1][j]
               (iii) Replace: value for i-1 and j-1 i.e arr[i-1][j-1]
           now take minimum of above three possibilities ,also show which type of operation performed over A.
          
           if arr[i][j-1] is minimum ,then operation is inserting a character at jth place in string A.
           if arr[i-1][j] is minimum ,then operation is removing a character at jth place in string A.
           if arr[i-1][j-1] is minimum .then operation is replacing a character at jth place in string A.
          
           arr[i][j]=( 1+ min(arr[i][j-1], arr[i-1][j], arr[i-1][j-1]));
   }
     
(3)finally return value at arr[m][n].

Time complexity = O(m*n)