From Recursion To Dynamic Programming

Dynamic programming is a really useful technique. When used appropriately, it saves processor time and memory space.

Shoot! After writing all the code for this entry, I just noticed that the Wikipedia entry for dynamic programming uses the same example I thought about using in this post. Oh well, let me just show you some code and explain just a little.

private int recursiveFib(int n)
{
  if (n == 0)
   return 0;
  if (n == 1)
   return 1;
  return recursiveFib(n - 1) + recursiveFib(n - 2);
}

The above code calculates the Fibonacci number for any integer n. The code is easy to read and effective. However, there's one problem: we repeat calls to recursiveFib even though we may have already computed a value. For example for n=4, we'll call recursiveFib(2) twice; this may not seem like a big problem but for larger Ns the number of unique calls to recursiveFib is very small. What a waste of processor cycles!

Now that we've realized we're wasting resources because the number of unique calls to our recursive methods is small, we're ready to move on to dynamic programming. Here's the dynamic code:

private int dynamicFib(int n)
{
  int[] dynamicArray = new int[n];
  dynamicArray[0] = 0;
  dynamicArray[1] = 1;
  for (int i = 2; i < n; i++)
  {
   dynamicArray[i] = dynamicArray[i - 1] + dynamicArray[i - 2];
  }
  return dynamicArray[n];
}

Even though this code may not be as succinct as the recursive code, it saves resources. By taking a bottom up approach (rather than the top to bottom approach of the recursive method) and saving our previous calculations, we never have to recompute a value again! Although, with oil being as cheap as it is nowadays, you may not really care.

In summary:
If you want to solve a problem with dynamic programming, I recommend you first solve it recursively. This may seem like a waste of time, but you need the recursive solution to spot where the improvement to the algorithm needs to occur. Once you've figured that out, all you have to do is compute and store you partial solutions as you go.