/*
**	Dynamic Programming, very similar to longest common substring question
**
**	dis[i,j] means the distance from transform s1s2..si to t1t2...tj
**	then the value of dis[i,j] should the minimus value of following:
**		d[i-1, j] + deletion		(just delete si to have d[i-1, j] situation)
**		d[i, j-1] + inserstion		(base on d[i, j-1], insert tj to s become d[i, j])
**		d[i-1, j-1]+substitution	(base on d[i-1,j-1], replace si with tj becom d[i, j])
*/


#include <iostream>
#include <string>

using namespace std;


int GetMin(int a, int b, int c)
{
	return a > b? (b > c? c : b) : (a > c? c : a);
}

int MinDistance(string source, string target) 
{
	int m = source.length()+1;
	int n = target.length()+1;
	
	int dis[m][n];
	
	for (int i = 0; i < m; ++i)
		dis[i][0] = i;
	for (int i = 0; i < n; ++i)
		dis[0][i] = i;
	
	for (int i = 1; i < m; ++i)
		for (int j = 1; j < n; ++j)
			dis[i][j] = GetMin(dis[i-1][j] +1, dis[i][j-1]+1
				, dis[i-1][j-1]+(source[i-1] == target[j-1]?0:1));

	return dis[source.length()] [target.length()];      
}

int main(int argc, char** argv)
{
	cout << MinDistance("abe" , "ace");
	return 0;
}