# LeetCode - 0583. Delete Operation for Two Strings
### 題目網址：https://leetcode.com/problems/delete-operation-for-two-strings/
###### tags: `LeetCode` `Medium` `動態規劃（Dynamic Programming）` `最小編輯距離（Minimum Edit Distance）`

/*
    -LeetCode format-
    Problem: 583. Delete Operation for Two Strings
    Difficulty: Medium
    
    by Inversionpeter
*/



int DP[501][501];

static const auto Initialize = []{
    ios::sync_with_stdio(false); cout.tie(nullptr);
    for (int i = 1; i < 501; ++i)
        DP[i][0] = DP[0][i] = i;
    return nullptr;
}();

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