7. Algorithm, Question, Explanation, Solution, at toptal.com : How would you, in general terms, describe dynamic programming? As an example, how would you find the length of the longest common subsequence of elements in two arrays by using this method? Use C++ .
By: Chrysanthus Date Published: 30 Oct 2025
Description of Dynamic Programming
Dynamic programming is a paradigm for solving optimization problems. It consists of finding solutions for intermediate subproblems, which can be stored and reused for solving the actual problem. Dynamic programming is the best approach for difficult problems that always become trivial once we know the solution for a slightly easier instance of that problem - the intermediate subproblem. Dynamic programming solutions are best represented by a recursive relation, and easily implemented.If the intermediate subproblems are not overlapping, then we have just a case of Divide and Conquer.
Many dynamic programming problems involves a two dimensional array, also called a matrix or a table. An attempt to deduce a logical pattern in the content of the 2D array is made, before the code of few number of operations, is written from the pattern.
Lesson
The longest common subsequence (LCS) is defined as the longest subsequence that is common to all the given sequences, provided that the elements of the subsequence are not required to occupy consecutive positions within the original sequences. The order of the elements should also be maintained.Illustration
Subsequences of "abc" are "", "a", "b", "c", "ab", "ac", "bc" and "abc". In general, a string of length n has 2n subsequences. In this case n is 3. Do not forget that "" of zero length is a subsequence. Note that in a sequence, some characters can be skipped, in the original string.
Longest Common Subsequence Examples
Output: 2
Explanation: The longest subsequence (lcs) which is present in both strings is "ac".
str1 = "aggtab"; str2 = "gxtxayb"
Output: 4
Explanation: The longest common subsequence (lcs) which is present in both strings is "gtab".
str1 = "abc"; str2 = "cba"
Output: 1
Explanation: There are three longest common subsequences of length 1, "a", "b" and "c".
Problem Illustration
Consider the strings: "sandal" with M number of characters, equal to 6, and the string "bananas" with N number of characters equal to 7. Each of these strings is considered an array.The longest common subsequence of characters is "ana". For "sandal", 'd' is skipped.
The Two Dimensional Dynamic Programming (dp) Array
The dp array is:b a n a n a s
i/j 0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
s 1 0 0 0 0 0 0 0 1
a 2 0 0 1 1 1 1 1 1
n 3 0 0 1 2 2 2 2 2
d 4 0 0 1 2 2 2 2 2
a 5 0 0 1 2 3 3 3 3
l 6 0 0 1 2 3 3 3 3
Explanation of the 2D dp Array
str1, "sandal" has the index , i from 0 to 6 inclusive, for a length of M+1. Index 0 refers to the empty string, "". Index 1 refers to the character, 's' as well as to the backward string "s". Index 2 refers to the character, 'a' as well as to the backward string "sa". Index 3 refers to the character, 'n' as well as to the backward string "san". Index 4 refers to the character, 'd' as well as to the backward string "sand". Index 5 refers to the character, 'a' as well as to the backward string "sanda". Index 6 refers to the character, 'l' as well as to the complete backward string "sandal".
str2, "bananas" has the index , i from 0 to 7 inclusive, for a length of N+1. Index 0 refers to the empty string, "". Index 1 refers to the character, 'b' as well as to the backward string "b". Index 2 refers to the character, 'a' as well as to the backward string "ba". Index 3 refers to the character, 'n' as well as to the backward string "ban". Index 4 refers to the character, 'a' as well as to the backward string "bana". Index 5 refers to the character, 'n' as well as to the backward string "banan". Index 6 refers to the character, 'a' as well as to the backward string "banana". Index 7 refers to the character, 's' as well as to the complete backward string "bananas".
"b a n a n a s"
"s a n d a l"
as there is no overlapping between the two strings. At this point, the common subsequence string is "",of zero length. If the lower string is shifted as a whole, one place to the right, the overlapping characters would be 'b' and 'l', and that gives rise to still a zero length common subsequence empty string. If the lower string is then shifted as a whole, one place to the right, the overlapping characters would be "ba" and "al", and that gives rise to a common subsequence string of length 1, with common subsequence character, "a". If the lower string is then shifted as a whole, one place to the right, the overlapping characters would be "ban" and "dal", and that gives rise to still a common subsequence string of length 1, with the common subsequence character, still "a". If the lower string is then shifted as a whole, one place to the right, the overlapping characters would be "bana" and "ndal", and that gives rise to a new common subsequence string of length 2, with the common subsequence "na", and 'd' skipped for the lower string part, "ndal". If the lower string is then shifted as a whole, one place to the right, the overlapping characters would be "banan" and "andal", and that gives rise to a common subsequence string of length 3, with the common subsequence "ana", and 'd' skipped for the lower string part, "andal". From this point, no matter how many steps the lower string is shifted to the right, the length of the common subsequence string will not increase, and their 3 characters will remain the same, in the same order.
And so, the length of the longest common subsequence is 3. The heading for the columns is "'b'a'n'a'n'a's'", with each letter representing a column. Column zero has no header character. All the 7 cells of column zero, each has the value, zero, because there is no overlapping between the two given strings.
In the table, there are 7 rows. The heading for the rows is "'s'a'n'd'a'l'", with each letter representing a row. Row zero has no header character. All the 8 cells of row zero, each has the value, zero, because there is no overlapping between the two given strings.
The variable for the indexes for the rows is i, and the indexes are from 0 to 6. The variable for the indexes for the columns is j, and the indexes are from 0 to 7. Do not confuse between the first useful column of zeros and the row index column with indexes from 0 to 6, in the table. Also, do not confuse between the first useful row of zeros and the column index row with indexes from 0 to 7, in the table.
For the first row of index 1 (i=1), the 's' alone of "sandal" is shifted one horizontal (j) index at a time from the left end of the row to the right end of the row. For each cell, the length of the common subsequence found is noted. This only occurs at the end of the last cell, with length 1. The overlapping same characters here are, the starting 's' in "sandal" and the last 's' of "bananas". At the end of the algorithm, this common 's' is not part of the longest common subsequence. However, the corresponding cell should have the value, 1.
For the second row of index 2 (i=2), "sa" of "sandal" is shifted one horizontal (j) index at a time from the left end of the row to the right end of the row. For each cell, the length of the common subsequence found is noted. This is 1 for dp[2][2], dp[2][3], dp[2][4], dp[2][5], dp[2][6] and dp[2][7]. The preceding cell of dp[2][1] has 0. The 1's are for the letter 'a' in "sa" of "sandal" and "ba" of "bananas".
For the third row (i=3), "san" of "sandal" is moved from the left end to the right end, one horizontal (j) index at a time. The value of 1 in cell dp[3][2] is for the 'a' in "san" of "sandal" and "ba" of "bananas". The rest of the cells in the row have value 2. The 2 is for "an" in "san" of "sandal" and "ban" of "bananas".
The Code
It is important to note that the indexes for the words, "sandal" and "bananas", with the indexes for the dp 2D array, have a difference of 1. For example, the i index for 's' in "sandal" is 0, while the dp i index for the same 's' in "sandal" is 1. The j index for 'b' in "bananas" is 0, while the dp j index for the same 'b' in "bananas" is 1. With that scheme, the complete table with the two index scales is:
b(0) a(1) n(2) a(3) n(4) a(5) s(6)
i/j 0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
s(0) 1 0 0 0 0 0 0 0 1
a(1) 2 0 0 1 1 1 1 1 1
n(2) 3 0 0 1 2 2 2 2 2
d(3) 4 0 0 1 2 2 2 2 2
a(4) 5 0 0 1 2 3 3 3 3
l(5) 6 0 0 1 2 3 3 3 3
Looking at the columns: Index 3 for example, for second 'a' in "bananas" is dp index 4 - 1. So, to go from a column index to a character index in "bananas", subtract 1, for the same position. j is the variable for dp column indexes.
Looking at the rows: Index 3 for example, for 'd' in "sandal" is dp index 4 - 1. So, to go from a row index to a character index in "sandal", subtract 1, for the same position. i is the variable for dp row indexes.
The Logical Pattern
There are two rules to deduce here, which are alternatives to one another.Rule 1
Let str1 identify "sandal" and str2 identify "bananas". If for a cell in the 2-dimensional array, the corresponding letters in the rows header ("sandal") and columns header ("bananas") are the same, then in order to obtain the number (answer) for that cell, go to the immediate left-top cell; get the number there and add 1 to it. This is true for the following cells:
For str1[0] = str2[6] = 's' , dp[1][7] = 1 = dp[0][6] + 1 .
For str1[1] = str2[1] = 'a' , dp[2][2] = 1 = dp[1][1] + 1 .
For str1[1] = str2[3] = 'a' , dp[2][4] = 1 = dp[1][3] + 1 .
For str1[1] = str2[5] = 'a' , dp[2][6] = 1 = dp[1][5] + 1 .
For str1[2] = str2[2] = 'n' , dp[3][3] = 2 = dp[2][2] + 1 .
For str1[2] = str2[4] = 'n' , dp[3][5] = 2 = dp[2][4] + 1 .
For str1[4] = str2[1] = 'a' , dp[5][2] = 1 = dp[4][1] + 1 .
For str1[4] = str2[3] = 'a' , dp[5][4] = 3 = dp[4][3] + 1 .
For str1[4] = str2[5] = 'a' , dp[5][6] = 3 = dp[4][5] + 1 .
Rule 2
Rule 2 is the alternative to rule 1. If rule 1 does not hold (the corresponding letters are not the same), then the number (answer) for the cell in question, is the bigger of the two numbers of the immediate left cell and immediate top cell. Note that if the numbers of these two (left and top) cells are the same, the bigger is still that same number.
The Program
And so the code is (read the comments as well):
#include <iostream>
#include <algorithm> //for max() function
#include <string>
using namespace std;
int lcs(string str1, string str2, int M, int N) { //M for str1 and N for str2
int dp[M+1][N+1]; //M for rows and N for columns
for (int i=0; i<(M+1); i++) //initialize first column
dp[i][0] = 0;
for (int j=0; j<(N+1); j++) //initialize first row
dp[0][j] = 0;
for (int i=1; i<(M+1); i++) {
for (int j=1; j<(N+1); j++) {
if (str1[i-1] == str2[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[M][N];
}
int main()
{
string str1 = "sandal";
string str2 = "bananas";
int ret = lcs(str1, str2, 6, 7);
cout << ret << endl;
return 0;
}
#include <algorithm> //for max() function
#include <string>
using namespace std;
int lcs(string str1, string str2, int M, int N) { //M for str1 and N for str2
int dp[M+1][N+1]; //M for rows and N for columns
for (int i=0; i<(M+1); i++) //initialize first column
dp[i][0] = 0;
for (int j=0; j<(N+1); j++) //initialize first row
dp[0][j] = 0;
for (int i=1; i<(M+1); i++) {
for (int j=1; j<(N+1); j++) {
if (str1[i-1] == str2[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[M][N];
}
int main()
{
string str1 = "sandal";
string str2 = "bananas";
int ret = lcs(str1, str2, 6, 7);
cout << ret << endl;
return 0;
}
The output is:
3
The time complexity for the solution is O(MxN). The space complexity is also given as O(MxN).
Thanks for reading.
3
The time complexity for the solution is O(MxN). The space complexity is also given as O(MxN).
Thanks for reading.