【Leetcode】72. Edit Distance(동적 계획)(2019 맞춤법 필기시험)(중점)

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:

Insert a character

Delete a character

Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

제목 대의:
두 개의 문자열을 주면 우리는 세 가지 조작을 통해 1. 교체해야 한다.2. 삽입;3. 삭제.최소한의 조작 절차를 통해 워드1을 워드2로 바꾼다.
문제 해결 방법:
이 문제는 매우 은밀한 DP이지만 우리는 세 가지 조작에서 동적 기획의 흔적을 볼 수 있다.일단 설명 안 해.
4/22: 우리는 첫 번째 열, 첫 줄의 초기화 행위를 빈 문자열에서 현재 목표까지 조작하는 데 필요한 단계로 볼 수 있다.각 위치의 초기화는 같으면 바로 다음 단계의 보수, 즉 대각선의 값을 얻는다.만약 같지 않으면 제시된 세 가지 상황이 나타난다. (1) 대각선에서 출발한다. 즉, 이전 답안에 새로운 문자를 삽입하여 현재의 목표 문자열을 만족시키도록 한다.(2) 기존 문자열에서 출발하여 현재 위치를 삭제하여 현재 목표 문자열을 만족시키도록 한다.(3) 목표 문자열에서 출발하여 현재 위치를 바꾸어 현재 목표 문자열을 만족시키도록 한다.

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