#### 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;
}```