Dynamic Programming - Lifeline of Technical interviews - 2

In the previous post, we discussed what dynamic programming is, why dynamic programming solution is better, how to identify the problem and how to tackle them.

In this post, we will be solving some problems on dynamic programming that have been asked in Google interviews previously. To get better results, I will encourage you to spend at least 20 minutes on finding the solution to the problem by yourself before moving on to the solution part and even if you see the solution part try to code it up on your own.

Unlike my last post on Graph problems, I will only be discussing the idea to solve the problem and not provide with the solution code. I will encourage you to try to write the code on your own and get them accepted on the link provided — it will be fun game

Problem 1:

• In this problem, the DP state will only contain the index in the given array so with our DP array, let's say that DP[i] denotes if it is possible to reach the index i.
• Initialize DP array of length n to false with DP[0] = true, as you are already at this position.
• If you can reach the index I, then you can reach all of the indexes min( i+arr[i], n-1 ), so update, the DP array according to that.
• If DP[n-1] is true, then return true, else false.

Problem 2

• 90% of the problems under the category of DP on the string will have the same DP state where DP[i][j] represent the value of the target variable for the prefix of length i of one string and prefix of length j of another string.
  So in this example, DP[i][j] represents the number of ways of converting first i characters of string1 into first j characters of string2.
  string1 = "rabbbit"
  string2 = "rabit"
  DP[3][2] represents the number of ways of converting string "rabb" into the string "rab."

• Let's look at the DP transitions now, if you are on DP state (i,j), then we have two cases to consider.

  → string1[i] != string2[j]
  Since both characters do not match, it means we will have to skip the ith character from the string1. and the number of ways for the state (i,j) will be same as that of state (i-1,j) so in that case, we can write that
  dp[i][j] = dp[i-1][j]

  → string1[i] = string2[j]
  Since the characters are same we can match up the ith index from string1 to jth of string2. Hence the number of ways will be same as that of state (i-1,j-1) since we are just extending our match by including one more index from both the strings. In this case, even if the characters do match, we still have the liberty to skip the ith char from the string1, it means we also need to consider the number of ways of state (i-1,j).
  dp[i][j] = dp[i-1][j] + dp[i-1][j-1]

  → one base case we need to handle separately will be of
  dp[i][0] = 1
  means the number of ways of converting first i chars of string1 into an empty is only 1, that skips all the charaters.

• DP[n][m] will hold our final answer. Where n is the length of first string and m is length of the second string.

Problem 3

• Again just like the last problem, the DP state will be same. State DP[i][j] represents the number of operations requires converting the first i chars of string1 into first j chars of string2.

• Let's look at the DP transitions now, just like the last time we have two cases,

  → string1[i] = string2[j]
  Now since the two characters match up, we do not need to perform any operation on them, hence the number of operations required to reach the state (i,j) will be same of that of state (i-1,j-1).

  dp[i][j] = dp[i-1][j-1]

  → string1[i] != string2[j]

  We have some cases here.

  1. Delete the ith char from the first string1, in that case, we will have
     dp[i][j] = 1 + dp[i-1][j] // 1 + number of operation till state (i-1,j)

  2. Insert the char into string2, in that case, we will have
     dp[i][j] = 1 + dp[i][j-1] // 1 + number of operations till state (i,j-1)

  3. Convert the chars to match up. in that case, we will have.
     dp[i][j] = 1 + dp[i-1][j-1] // 1 + number of operations till state (i-1,j-1)

  4. Now since we want to minimize the number of operations at each step, hence we will have:
     dp[i][j] = 1 + min( dp[i-1][j], dp[i][j-1], dp[i][j])

  5. handle base cases for i == 0 or j ==0 seperately.
     if( i == 0 ) dp[i][j] = j // delete all the j chars
     if( j == 0 ) dp[i][j] = i // insert all the i chars.

• Just like the last time, DP[n][m] will hold our final answer for the problem.

Problem 4

• In this problem, first of all, let's construct a 2-D array isPalindrome, such that isPalindrome[i][j] = 1 if substring [i,j] is a palindrome and isPalindrome[i][j] = 0 otherwise.

• To determine whether substring [i,j] is palindrome or not, we have:

    if( i == j ) isPalindrome[i][i] = 1
    else if( j-i == 1) isPalindrome[i][j] = str[i] == str[j]
    else if( str[i] != str[j] ) isPalindrome[i][j] = 0;
    else if( str[i] == str[j] ) isPalindrome[i][j] = isPalindrome[i+1][j-1]
  

• Notice that for calculating the isPalindrome for the state (i,j), we need the information from the state (i+1, j-1), meaning we need to have information about the substring of smaller length to solve the problem for substrings of larger lengths. While filling up the two-dimensional table for single, you will encounter it a lot of time just like in "Longest palindromic subsequence" you move on from working on smaller substring to larger substrings.

  intialise isPalindrome to false.
  for( len = 1 ; len <= n ; len++)
  {
     for(i = 0 ; i + len  <= n ; i++)
     {
        j = i + len - 1
        if( len ==1 ) isPalindrome[i][i] = 1
        else if( len ==2 ) isPalindrome[i][j] = str[i] == str[j]
        else isPalindrome[i][j] = (str[i] == str[j]) && isPalindrome[i+1][j-1];
     }
  }

• Now, let's consider our original problem of "Palindrome partioning", let's say that DP[i] represents the number of cuts needs to partition the prefix of length i into palindromes, now when calculating the DP[i], we know the value of DP[j] for all j < i, so for some j is the the substring str[j+1:i] is a palindrome then we can say that
  dp[i] = dp[j] + 1 // number of partition needed till j ( already calculated ) + one more parition for the substring[j+1:i]
  Since we want to minimize the value of dp[i], hence we will try this out for all such j available to us and choose the minimum among them.

• dp[n-1] will hold the answer to our problem.