🙏

জয়  শ্রী  রাম

🕉

---

From my several years of experience with solving Dynamic Programming, I found that there is a pattern to the solutions of most Dynamic Programming problems that involve two strings. Knowing this template will help you think in a very mechanical way and nailing an optimized DP solution in just a few minutes. Mechanical way of thinking during exams or interviews is not bad. It takes immense practice, prior experience, critical thinking and deep understanding of the core concept to reach the state that your expertise enables you to mechanically solve a certain problem without thinking much on spot. In fact, as you advance in your career, your ability to observe patterns will help you stand out of the crowd and be known as a high-calibre exceptional developer.

General problem statement for this kind of DP problems will vary but most of the time you are given two strings s1 with length m and s2 with length n, and you need to return some result.

Approach:

Most of the problems with this pattern can be solved in in O(n * m) complexity.
For all substrings (starting from the first character) of s1 starting from substring-length of 1 to all the way up to m, we would compute the result for all substrings (starting from the first character) of s2 of substring-length of 1 to n. Since we do in the increasing order of length, whenever we need DP result for a shorter length substrings to compute DP result for a longer length substring (Optimal substructure property), the result for the shorter length substring would already be available and ready to use (assuming you are either memoizing or doing bottom-up tabulation). This eventually will get you the result for the full length of the two given strings.

In most DP problems involving 2 strings, whenever you are considering two substrings from given two strings, concentrate on what happens when the last characters of the two substrings are same, i.e, matching. This would help you getting the recurrence DP relationship. Since we are considering the last character of the substrings, we would see that for some problems we are naturally thinking in terms of suffix, and that is definitely the right way of thinking. This whole concept would become very clear as we start looking at examples in next few chapters.

T[][] dp = new T[m + 1][n + 1]; // dp[0][0] represents 0 length of str1 and 0 length str2

Next, initialize dp[i][j] for all j when i = 0. This represents all
 cases when we take 0 length of str1, i.e, when str1 is empty.

Next, initialize dp[i][j] for all i when j = 0. This represents all
 cases when we take 0 length of str2, i.e, when str2 is empty.


// i - indexing string str1 with length m
// j - indexing string str2 with length n
for (int i = 1; i <= m; i++) {
   for (int j = 1; j <= n; j++) {
       if (str1[i - 1] == str2[j - 1]) {
           dp[i][j] = /*code*/;
       } else {
           dp[i][j] = /*code*/;
       }
   }
}

Instructor: