UVa 1207 - AGTC

// UVa 1207 - AGTC
#include <iostream>
#include <string>
using namespace std;

int calculateEditDistance(const string& a, const string& b) {
	int lenA = a.length(), lenB = b.length();
	int T[lenA + 1][lenB + 1];

	// base cases
	for (int i = 1; i <= lenA; i++)
		T[i][0] = i;
	for (int j = 1; j <= lenB; j++)
		T[0][j] = j;
	T[0][0] = 0;

	// dynamic programming
	for (int i = 1; i <= lenA; i++)
		for (int j = 1; j <= lenB; j++)
			if (a[i - 1] == b[j - 1])
				T[i][j] = T[i - 1][j - 1];
			else
				T[i][j] = min(min(T[i][j - 1], T[i - 1][j]), T[i - 1][j - 1]) + 1;
	return T[lenA][lenB];
}

int main() {

	int ignore;

	while (cin >> ignore) {
		string a, b;
		cin >> a >> ignore >> b;

		cout << calculateEditDistance(a, b) << endl;
	}

	return 0;
}