Ever seen your kitten sitting and wonder what will be the minimum number of operations (insertion, deletion, replacement) of manipulating the characters to change the word "kitten" to "sitting"? Definitely not, which is exactly why it is a Dynamic Programming question.

As the good ol' protocol goes, any tutorial or blog on DP needs to first state that brute force bad betch and we gotta just look at recursion before proposing a wild way to solve the problem no one could think of. So here we go with recursion first:

// Base Case
If i == 0, return j → insert all j characters of s2.
If j == 0, return i → delete all i characters of s1.

If A[i-1] == B[j-1]:
    dp[i][j] = dp[i-1][j-1]  // Characters match, no extra cost
Else:
    dp[i][j] = 1 + min(
        dp[i-1][j],     // Delete from A
        dp[i][j-1],     // Insert into A  
        dp[i-1][j-1]    // Substitute in A
    )

Makes sense! No operation if match, else find which of the three operations comes with the least amount of emotional baggage. Let's have a small dry run where s1 = "abc" and s2 = "adc":

edit(3,3): s1[2]='c', s2[2]='c' → match → edit(2,2)
--------------------------------------------------------
edit(2,2): s1[1]='b', s2[1]='d' → mismatch:
    -> Insert d:     1 + edit(2,1)
    -> Delete b:     1 + edit(1,2)
    -> Replace b→d:  1 + edit(1,1)
--------------------------------------------------------
edit(2,1): s1[1]='b', s2[0]='a' → mismatch:
    -> Insert a:     1 + edit(2,0) = 1 + 2 = 3
    -> Delete b:     1 + edit(1,1)
    -> Replace b→a:  1 + edit(1,0) = 1 + 1 = 2
--------------------------------------------------------
edit(1,1): s1[0]='a', s2[0]='a' → match → edit(0,0) = 0

So:
edit(1,1) = 0
edit(2,1) = min(3, 1 + 0 = 1, 2) = 1
--------------------------------------------------------
edit(1,2): s1[0]='a', s2[1]='d' → mismatch:
    -> Insert d:     1 + edit(1,1) = 1
    -> Delete a:     1 + edit(0,2) = 3
    -> Replace a→d:  1 + edit(0,1) = 2

edit(1,2) = min(1, 3, 2) = 1
--------------------------------------------------------
edit(1,1) we already know = 0

So:
edit(2,2) = min(1 + 1, 1 + 1, 1 + 0) = min(2, 2, 1) = 1
--------------------------------------------------------
edit(3,3) = edit(2,2) = 1

Our guy here now has a time complexity of O(3 ^ (min(m,n))) because each recursive call splits into three or more calls (insert, replace, delete)

And just for formality's sake, here's the memoised version:

int editDistance(string& s1, string& s2, int i, int j, vector<vector<int>>& dp) {
    if (i == 0) return j;
    if (j == 0) return i;
    if (dp[i][j] != -1) return dp[i][j];

    if (s1[i - 1] == s2[j - 1])
        return dp[i][j] = editDistance(s1, s2, i - 1, j - 1, dp);

    int insertOp = 1 + editDistance(s1, s2, i, j - 1, dp);
    int deleteOp = 1 + editDistance(s1, s2, i - 1, j, dp);
    int replaceOp = 1 + editDistance(s1, s2, i - 1, j - 1, dp);

    return dp[i][j] = min({insertOp, deleteOp, replaceOp});
}

If you need help understanding this, ngmi. Anyway, that was a pathetic excuse of a DP solution, here's the real one:

Consider the dp[i][j] state. In the recursive solution, dp[i][j] represents the minimum edit distance between the first i characters of s1 and the first j characters of s2.

The base cases for our recursion were:

dp[i][0] = i: To transform s1[0...i-1] into an empty string (s2 up to 0 characters), you need to delete all i characters from s1.
dp[0][j] = j: To transform an empty string (s1 up to 0 characters) into s2[0...j-1], you need to insert all j characters of s2.

These base cases naturally form the first row and first column of our DP table. Now, let's look at the recurrence relation:

If s1[i-1] == s2[j-1]:
    dp[i][j] = dp[i-1][j-1] #No operation needed, cost is inherited from the previous match)
Else (s1[i-1] != s2[j-1]):
    dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

Let's dissect the three operations in the else case and how they relate to the DP table:

1 + dp[i-1][j] (Delete from s1): This means we are considering deleting the character s1[i-1]. If we delete s1[i-1], then the problem reduces to finding the edit distance between s1[0...i-2] and s2[0...j-1]. This is precisely what dp[i-1][j] represents. We add 1 for the deletion operation. "To make s1[0...i-1] match s2[0...j-1], I'll delete s1[i-1] and then find the distance between the remaining s1 prefix and all of s2's prefix."

1 + dp[i][j-1] (Insert into s1): This means we are considering inserting a character into s1 to match s2[j-1]. After inserting, the problem reduces to finding the edit distance between s1[0...i-1] and s2[0...j-2]. This is dp[i][j-1]. We add 1 for the insertion operation. "To make s1[0...i-1] match s2[0...j-1], I'll insert a character (matching s2[j-1]) at the end of s1 and then find the distance between s1's current prefix and s2's remaining prefix."

1 + dp[i-1][j-1] (Replace in s1): This means we are considering replacing s1[i-1] with s2[j-1]. After replacing, both characters are effectively matched, and the problem reduces to finding the edit distance between s1[0...i-2] and s2[0...j-2]. This is dp[i-1][j-1]. We add 1 for the replacement operation. "To make s1[0...i-1] match s2[0...j-1], I'll replace s1[i-1] with s2[j-1] and then find the distance between the remaining prefixes of both strings."

The tabulation approach builds the DP table iteratively, starting from the base cases and moving towards dp[m][n]. Each dp[i][j] value is computed using values from its "left" (dp[i][j-1]), "up" (dp[i-1][j]), and "top-left diagonal" (dp[i-1][j-1]). This ensures that when we compute dp[i][j], all the required previous subproblem results are already available.

So with your sitting kitten example:

s1 = "kitten", m = 6
s2 = "sitting", n = 7

We'll create a (m+1) x (n+1) DP table. The rows correspond to prefixes of s1 and columns to prefixes of s2. dp[i][j] stores the minimum operations to transform s1[0...i-1] to s2[0...j-1].

The first row (i=0) represents transforming an empty string to prefixes of s2. This requires j insertions.

The first column (j=0) represents transforming prefixes of s1 to an empty string. This requires i deletions.

      ""  s   i   t   t   i   n   g
   ---------------------------------
"" |  0   1   2   3   4   5   6   7
k  |  1   ?   ?   ?   ?   ?   ?   ?
i  |  2   ?   ?   ?   ?   ?   ?   ?
t  |  3   ?   ?   ?   ?   ?   ?   ?
t  |  4   ?   ?   ?   ?   ?   ?   ?
e  |  5   ?   ?   ?   ?   ?   ?   ?
n  |  6   ?   ?   ?   ?   ?   ?   ?

Now, let's fill the table step by step.

dp[1][1] (k -> s): s1[0] = 'k', s2[0] = 's'. Mismatch.

Delete 'k': 1 + dp[0][1] = 1 + 1 = 2

Insert 's': 1 + dp[1][0] = 1 + 1 = 2

Replace 'k' with 's': 1 + dp[0][0] = 1 + 0 = 1

dp[1][1] = min(2, 2, 1) = 1

dp[1][2] (k -> si): s1[0] = 'k', s2[1] = 'i'. Mismatch.

Delete 'k': 1 + dp[0][2] = 1 + 2 = 3

Insert 'i': 1 + dp[1][1] = 1 + 1 = 2

Replace 'k' with 'i': 1 + dp[0][1] = 1 + 1 = 2

dp[1][2] = min(3, 2, 2) = 2

     "" s  i  t  t  i  n  g
   ---------------------------------
"" | 0  1  2  3  4  5  6  7
k  | 1  1  2  3  4  5  6  7  (k!=s: 1+min(1,1,0)=1; k!=i: 1+min(2,1,1)=2; etc.)
i  | 2  2  1  2  3  4  5  6  (i!=s: 1+min(1,2,1)=2; i==i: dp[1][1]=1; etc.)
t  | 3  3  2  1  2  3  4  5  (t!=s: 1+min(2,3,2)=3; t!=i: 1+min(1,2,1)=2; t==t: dp[2][2]=1; etc.)
t  | 4  4  3  2  1  2  3  4  (t!=s: 1+min(3,4,3)=4; t!=i: 1+min(2,3,2)=3; t==t: dp[3][3]=1; etc.)
e  | 5  5  4  3  2  2  3  4  (e!=s: 1+min(4,5,4)=5; e!=i: 1+min(3,4,3)=4; e!=t: 1+min(2,3,2)=3; etc.)
n  | 6  6  5  4  3  3  2  3  (n!=s: 1+min(5,6,5)=6; n!=i: 1+min(4,5,4)=5; n!=t: 1+min(3,4,3)=4; n!=t: 1+min(2,3,2)=3; n==n: dp[5][4]=2; etc.)

Let's do a quick dry run for dp[5][5] (kitten[0...4] "kitte" vs sitting[0...4] "sitti")

s1[4] = 'e', s2[4] = 'i'. Mismatch.

We need to consider 3 options:

Delete 'e' from "kitte": Cost is 1 + dp[4][5]. dp[4][5] corresponds to transforming "kitt" to "sitti". From the table, dp[4][5] = 2. So, 1 + 2 = 3.

Insert 'i' into "kitte": Cost is 1 + dp[5][4]. dp[5][4] corresponds to transforming "kitte" to "sitt". From the table, dp[5][4] = 2. So, 1 + 2 = 3.

Replace 'e' with 'i': Cost is 1 + dp[4][4]. dp[4][4] corresponds to transforming "kitt" to "sitt". From the table, dp[4][4] = 1. So, 1 + 1 = 2.

dp[5][5] = min(3, 3, 2) = 2. This matches the table.

(no table support in my CMS yet, asked ChatGPT to generate this)

Finally, the answer for transforming "kitten" to "sitting" is dp[6][7], which is 3.

The operations are:
Replace 'k' with 's' (kitten -> sitten)
Replace 'e' with 'i' (sitten -> sittin)
Insert 'g' (sittin -> sitting)

Total 3 operations.

int minDistance(const string& s1, const string& s2) {
    int m = s1.length();
    int n = s2.length();

    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    for (int j = 0; j <= n; ++j) 
        dp[0][j] = j;
    for (int i = 0; i <= m; ++i) 
        dp[i][0] = i;

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (s1[i - 1] == s2[j - 1]) 
                dp[i][j] = dp[i - 1][j - 1];
            else 
                dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
        }
    }

    return dp[m][n];
}

Bye!