The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Dynamic Programming

Problem :-
Solve the Edit Distance problem.
Edit Distance between two strings is the cost involved in converting one string to another.
For conversion, we can use three kind of operations ( INSERT, DELETE & REPLACE ).
Assume the costs of insertion, deletion and replacing as 1.
So, the problem is to find out minimum number of edits required to convert one string to another.
For e.g, minimum edits required to convert sunflower to sunlight is 5

Solution :-
Suppose we need to convert a string ( str1 ) of size m to a string ( str2 ) of size n with minimum number of edits.
First we will consider a smaller subproblem and define an optimal structure of the solution.
Let Cost ( i , j ) denotes the minimum cost to convert first ' i ' characters of str1 to first ' j ' characters of str2.
There are 2 possibilities :
1 ) if str1 ( i ) == str2 ( j ) , problem is reduced to finding Cost ( i - 1 , j - 1 ) ( no edit required )
2 ) if str1 ( i ) != str2 ( j ) , then we can choose any of the following edit operations :
    Insert : problem reduces to finding Cost ( i , j - 1 ) + INSERT_COST
                i.e we insert the mismatched character and add the cost of insertion.
    Delete : problem reduces to finding Cost ( i - 1 , j ) + DELETE_COST
    Replace : problem reduces to finding Cost ( i - 1 , j - 1 ) + REPLACE_COST
Now, our objective is to find minimum edit cost i.e to minimize Cost ( i , j ) . So, we will consider the minimum of the values of above subproblems or possibilities and the optimal structure of the solution is defined as :
Cost ( i , j ) = min [ Cost ( i , j - 1 ) + I , Cost ( i - 1 , j ) + D , Cost ( i - 1 , j - 1 ) + R ] if str1 ( i ) != str2 ( j ) and
Cost ( i , j ) = Cost ( i - 1 , j - 1 ) if str1 ( i ) == str2 ( j )
Now, we can find Cost ( i , j ) for any values of i and j.
Finally, Cost ( m , n ) gives the required minimum edit cost to convert str1 to str2.

#include<iostream>
#include<cstring>

#define INSERT_COST 1
#define DELETE_COST 1
#define REPLACE_COST 1

using namespace std;

int min(int a,int b) {
   return ((a < b) ? a : b);
}

/* convert str1 to str2 with minimum edits(insert,delete,replace)
   suppose length(str1) = m and length(str2) = n
   cost(i,j) -> cost of converting str1[0...i-1] to str2[0...j-1]
   cost(m,n) -> cost of converting str1 to str2 
   Standard recursive formula for computing cost(m,n) :-
   cost(i,j) = min[cost(i-1,j)+D, cost(i,j-1)+I, cost(i-1,j-1)+R]
   D -> delete cost, I -> insert cost, R -> replace cost  */

int editDistance(char str1[],int size1,char str2[],int size2) {
   // cost matrix
   // row -> str1 & col -> str2
   int cost[size1][size2];
   int i,j;
   // initialize the cost matrix
   for (i=0;i<size1;i++) {
      for(j=0;j<size2;j++) {
         if (i == 0) {
            // source string is NULL
            // so we need 'j' insert operations
            cost[i][j] = j*INSERT_COST;
         } else if (j == 0) {
            // target string is NULL
            // so we need 'i' delete operations
            cost[i][j] = i*DELETE_COST;
         } else {
            cost[i][j] = -1;
         }
      }
   } //initialization done

   //compute cost(i,j) and eventually return cost(m,n)
   for(i=1;i<size1;i++) {
      for(j=1;j<size2;j++) {
         int x = cost[i-1][j] + DELETE_COST;
         int y = cost[i][j-1] + INSERT_COST;
         // if str1(i-1) != str2(j-1), add the replace cost
         // we are comparing str1[i-1] and str2[j-1] since
         // the array index starts from 0
         int z = cost[i-1][j-1] + (str1[i-1] != str2[j-1])*REPLACE_COST;
         // as per our recursive formula
         cost[i][j] = min(x, min(y,z));
      }
   }

   // last cell of the matrix holds the answer
   return cost[size1-1][size2-1];
}

//main
int main() {
   char str1[] = "sunflower";
   char str2[] = "sunlight";
   int size1 = strlen(str1);
   int size2 = strlen(str2);
   int min_cost = editDistance(str1,size1+1,str2,size2+1);
   cout<<"\nMinimum edits required to convert "<<str1<<
                                       " to "<<str2<<" is "<<min_cost;
   cout<<endl;
   return 0;
}

Back | Next

All problems on Dynamic Programming
* Find the nth term of fibonacci series
* Evaluate combination(n, r)
* Solve the Edit-Distance problem
* Longest Common Subsequence ( LCS ) problem
* Given a set of coin denominations, find the minimum number of coins required to make a change for a target value
* Longest Increasing Subsequence ( LIS ) problem
* Unbounded Knapsack problem
* 0/1 Knapsack problem
* Splitting a string into minimum number of palindromes