Recursion and Dynamic Programming Approach for Solving Problems

If we have access to solutions for smaller instances of a given problem definition, can we construct a required solution?

Dynamic programming (meaning dynamic scheduling in this sense) is a general approach for solving complex optimization problems that can be composed into overlapping sub-problems. Like divide-and-conquer , we solve a given problem by combining the solutions of multiple smaller problems.

We mentioned in the divide-and-conquer technique article that a problem is divided into two or more independent sub-problems thereby solving the original problem by recursively 'conquering' and solving the sub-problems and then combining them.

We can see that dynamic programming pretty much does the same thing as divide-and-conquer, but notice that the sub-problems can be overlapping, as opposed to being independent. Dynamic programming is more efficient than its counterpart in the way that it allows for re-use of intermediate results, and often dramatically reduces operational time complexity , albeit at the expense of resource complexity (memory/ space) and that should not slip our mind when making a decision for which approach to use.

We gave an example for a Fibonacci Sequence case study, when we were looking at understanding Big O Notation, that illustrates exactly why in dynamic programming we strive to solve a sub-problem once, storing its return value on the stack for re-use otherwise known as memoization.

The quote above sums it up on the importance of remembering what we have computed, and of course this needs not to be overdone remembering that we are also introducing an O(n) complexity here in another dimension: space.

The key to solving a problem using dynamic programming efficiently is to give it a good thought when breaking the problem into sub-problems.

We must have it in our mind that there are many ways of coming up with sub-problems, and we must strive to develop a knack for doing that in the best way possible such that we need to solve as few sub-problems as possible, and more importantly that the bigger problem can be solved relatively easily once our sub-problems' solutions are found.

As we solve more and more problems, we will find that it maybe to the best of our interest to solve a slightly different problem than our original problem in a problem solving technique called Variation, that we will look at in a consecutive article.

Case Study: Simple Auto Suggestion using Longest Common Sub-sequence

Autosuggestion functionality using longest common sub-sequence explained exhaustively here.

The longest common sub-sequence (LCS) problem is the problem of finding the longest sub-sequence common to all sequences in a set of sequences (often just two sequences), and in our case the two sequences are a typed word on an application and any words that we have placed in our t9Dictionary.txt as shown below:

public static IEnumerable<string> AutoSuggest(string typedWord)
{
  StreamReader sr = new StreamReader("C:\\Projects\\t9Dictionary.txt");
  string vocabList = sr.ReadToEnd();
  sr.Close();
  var query = vocabList.Split(new[] { '\r', '\n', ' ' }, 
                                     StringSplitOptions.RemoveEmptyEntries)
            .Select(t => t.Trim());
//Returns top 5 most likely word suggestions
  return query
         .Where(word => LongestCommonSubsequence(typedWord, word)
         .Equals(word))
         .OrderByDescending(word => word.Length)
         .ThenByDescending(word => word)
         .Take(5);
}

The longer the word, the higher the probability of it being the intended word. That is why we sort matching words by length in descending order. The resulting IEnumerable of suggested words are sorted alphabetically in descending order so that we preserve the prefix(if a user started typing with a letter k, chances are the intended word also starts with a k).

LongestCommonSubsequence() function comparing a typed word and a vocabulary item used in the AutoSuggest() method above.

public static string LongestCommonSubsequence
  (this string typedWord, string vocabItem)
  {
    List<char> lcs = new List<char>();
    StringBuilder sb = new StringBuilder();

    typedWord = " " + typedWord;
    vocabItem = " " + vocabItem;
    int[,] T = CreateLcsMatrix(typedWord, vocabItem);

    int typedWordLength = typedWord.Length;
    int vocabItemLength = vocabItem.Length;
    int i = typedWordLength - 1;
    int j = vocabItemLength - 1;
         
    while (i > 0 && j > 0)
    {
      if (T[i, j] == T[i - 1, j - 1] + 1 && typedWord[i] == vocabItem[j])
      {
        lcs.Add(typedWord[i]);
        i--;
        j--;
      }
      else if (T[i - 1, j] > T[i, j - 1])
      {
        i--;
      }
      else
          j--;
     }

     for (int p = lcs.Count - 1; p >= 0; p--)
     {
       sb.Append(lcs[p].ToString());
     }

     return sb.ToString();
   }

Creating Longest Common Sub-sequence score Matrix used above

private static int[,] CreateLcsMatrix(string typedWord, string vocabItem)
{
   int typedWordLength = typedWord.Length;
   int vocabItemLength = vocabItem.Length;
   int[,] T = new int[typedWordLength, vocabItemLength];

   for (int i = 0; i < typedWordLength; i++)
   {
     T[i, 0] = 0;
   }

   for (int i = 0; i < vocabItemLength; i++)
   {
     T[0, i] = 0;
   }
            
   for (int i = 1; i < typedWordLength; i++)
   {
     for (int j = 1; j < vocabItemLength; j++)
     {
       if (typedWord[i] == vocabItem[j])
             T[i, j] = T[i - 1, j - 1] + 1;
       else
             T[i, j] = Math.Max(T[i, j - 1], T[i - 1, j]);
     }
    }
   return T;
}

Until the next article, happy problem solving!