Dynamic Programming - 2D

Longest Common Subsequence

Given two strings x and y, find the longest common subsequence (LCS) and print its length. (For string ABCBDAB and BDCABC, BCAB is the LCS, so return 4).

1
2
3
4
5
6
7
8
for(i = 0; i <= n; i++) D[i][0] = 0;
for(j = 0; j <= m; j++) D[0][j] = 0;
for(i = 1; i <= n; i++) {
for(j = 1; j <= m; j++) {
if(x[i] == y[j]) D[i][j] = D[i-1][j-1] + 1;
else D[i][j] = max(D[i-1][j], D[i][j-1]);
}
}

Edit Distance

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. 3 operations are permitted on a word: insert, delete or replace a character.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
for (int i=0; i<=m; i++)
{
for (int j=0; j<=n; j++)
{
// If first string is empty, only option is to
// isnert all characters of second string
if (i==0) dp[i][j] = j; // Min. operations = j

// If second string is empty, only option is to
// remove all characters of second string
else if (j==0) dp[i][j] = i; // Min. operations = i

// If last characters are same, ignore last char
// and recur for remaining string
else if (str1[i-1] == str2[j-1])
dp[i][j] = dp[i-1][j-1];

// If last character are different, consider all
// possibilities and find minimum
else dp[i][j] = 1 + min(dp[i][j-1], // Insert
dp[i-1][j], // Remove
dp[i-1][j-1]); // Replace
}
}