[LeetCode] Edit Distance 편집 거리

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a characterb) Delete a characterc) Replace a character
 
이 문제는 한 문자열에서 다른 문자열로 전환하는 데 필요한 변환 절차를 세 가지 변환 방식으로 한다. 한 문자를 삽입하고 한 문자를 삭제하며 한 문자를 바꾸는 것이다.과거의 경험에 따르면 문자열과 관련된 문제는 십중팔구 동적 기획 동적 프로그래밍으로 풀었는데 이 문제도 예외가 아니다.이 문제는 2차원 그룹 dp를 유지해야 합니다. 그 중에서 dp[i][j]는word1의 전 i자에서word2의 전 j자로 전환하는 데 필요한 절차를 나타냅니다.그러면 우리는 먼저 이 2차원 그룹 dp의 첫 번째 줄에 값을 부여할 수 있다. 이것은 매우 간단하다. 첫 번째 줄과 첫 번째 열에 대응하는 문자열이 항상 비어 있기 때문에 전환 절차는 완전히 다른 문자열의 길이이다.이전의 DP 제목과 유사하지만 어려운 점은 점차적인 추론식을 찾아내는 것이다. 예를 들어 워드1은'bbc'이고word2는'abcd'이다. 그러면 우리는 dp수조를 다음과 같이 얻을 수 있다.
 

  Ø a b c d
Ø 0 1 2 3 4
b 1 1 1 2 3
b 2 2 1 2 3
c 3 3 2 1 2

 
우리는 관찰을 통해 알 수 있듯이 word1[i]=word2[j]시 dp[i][j]= dp[i-1][j-1], 다른 경우 dp[i][j]는 왼쪽, 왼쪽 위, 위의 세 가지 값 중 가장 작은 값에 1을 더하면 점차적으로 다음과 같다.
dp[i][j] =      /   dp[i - 1][j - 1]                                                                   if word1[i - 1] == word2[j - 1]
                 \   min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1            else
 

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1 = word1.size(), n2 = word2.size();
        int dp[n1 + 1][n2 + 1];
        for (int i = 0; i <= n1; ++i) dp[i][0] = i;
        for (int i = 0; i <= n2; ++i) dp[0][i] = i;
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
                }
            }
        }
        return dp[n1][n2];
    }
};