최소 편집 알고리즘

최소 편집하는 횟수를 측정하는 유사 단어 검색 하는 알고리즘 이런거 ...와 유사함 https://www.acmicpc.net/problem/15483

주 컨셉은 DP 로 .. 계속 tistory vs test 와의 단어에서 최소 몇번만에.. 편집이 가능한지..  찾는 문제 

 

'
int solve(string & input1, string &input2)
{

	int len_a, len_b;

	len_a = input1.length();
	len_b = input2.length();

	for (int i = 0; i <= len_a; i++)
		dist[i][0] =i;

	for (int i = 0; i <= len_b; i++)
		dist[0][i] = i ;

	for (int i = 1; i <= len_a; i++) {

		for (int j = 1; j <= len_b; j++) {
			if (input1[i - 1] == input2[j - 1]) dist[i][j] = dist[i - 1][j - 1];
			else dist[i][j] = min(dist[i - 1][j - 1] + 1, min(dist[i][j - 1] + 1, dist[i - 1][j] + 1));

		}
	}

	return dist[len_a][len_b];
}