using System;

public class Program

{

    public static void Main()

    {

        Console.WriteLine(MinDistance("abc", "adc"));

    }

    public static int MinDistance(string word1, string word2) {

        int m = word1.Length;

        int n = word2.Length;

        int[,] M = new int[m+1, n+1];

        //Base Cases

        //Last Column

        for(int i=m; i >=0; i--)

        {

            M[i, n] = m-i;

        }

        //Last Row

        for(int i=n; i >=0; i--)

        {

            M[m, i] = n-i;

        }

        for(int i=m-1; i >=0; i--)

        {

            for(int j=n-1; j >=0; j--)

            {

                if(word1[i] == word2[j])

                    M[i,j] = M[i+1, j+1];

                else

                {

                    M[i,j] = 1+Math.Min(M[i+1,j], M[i,j+1]);

                }

            }            

        }

        return M[0,0];

    }

}