leetcode583

public class Solution {
    public int MinDistance(string word1, string word2) {
        int[,] dp = new int[word1.Length + 1, word2.Length + 1];
            for (int i = 0; i <= word1.Length; i++)
            {
                for (int j = 0; j <= word2.Length; j++)
                {
                    if (i == 0 || j == 0) dp[i, j] = 0;
                    else dp[i, j] = (word1[i - 1] == word2[j - 1]) ? dp[i - 1, j - 1] + 1
                            : Math.Max(dp[i - 1, j], dp[i, j - 1]);
                }
            }
            int val = dp[word1.Length, word2.Length];
            return word1.Length - val + word2.Length - val;
    }
}

https://leetcode.com/problems/delete-operation-for-two-strings/#/solutions

思路：本题使用动态规划，将问题转化为求：最长公共子序列。