Skills every programmer should have #1: Dynamic programming

During this course I'll try and describe several techniques and skills that every programming should have. Many of these subjects involve concepts that save a lot of time and provide easier solutions to problems than ad-hoc ones. If you have any suggestions, please let me know!

Dynamic programming

Dynamic programming is the first skill that every programmer should have. It can be used when you have a problem that can be split up into sub-problems that you've already calculated and cached. I have used it in numerous situations, including optimal control theory problems and Project Euler problems. An example:

Imagine you want to write an application that prints the factorial for every number up to N, so:

0! 1! 2! 3! ... N!

A naive solution would be

public class Main {
 public static long fac(int n) {
  if (n <= 1) {
   return 1;
  }

  return n * fac(n - 1);
 }

 public static void main(String[] args) {
  for (int i = 0; i < 10; i++) {
   System.out.println(fac(i));
  }
 }
}

This becomes very slow if N is large (in this example you can't make N too large, because the long overflows very quickly. Use BigInteger instead). However, if we look at the factorial function, we see that if we calculate 10!, we're recalculating 9!. We see that 10! = 10 * 9!. In general:

N! = N * (N-1)!

If we were to cache n! in a map, we'd be able to significantly reduce computation time. An improved solution:

public class Main {
 static Map<Integer, Long> facs = new HashMap<Integer, Long>();

 public static long fac(int n) {
  if (facs.containsKey(n)) {
   return facs.get(n);
  }
  
  if (n <= 1) {
   return 1;
  }

  long result = n * fac(n - 1);
  /* Add factorial to map. */
  facs.put(n, result);
  
  return result;
 }

 public static void main(String[] args) {

  for (int i = 1; i < 10; i++) {
   System.out.println(fac(i));
  }
 }
}

This is what's called dynamic programming and it is very useful to make seemingly infeasable solutions possible in exchange for memory. Let's look at a realistic example.

Best path in a triangle

Imagine you have a triangle like this:

   3
  7 4
 2 4 6
8 5 9 3

and you're aked to calculate the path with the optimal score. The score is calculated by adding all the numbers you go through. In this case the optimal score is 3 + 7 + 4 + 9 = 23. Note that this is problem 67 of the Euler Project, so if you want to try it for yourself first, you should stop reading here!

 This problem is easy to solve for small triangles, but for big triangles it becomes infeasable to calculate all the routes. We're now going to look at a triangle with a depth of 100. This means that there are 2^99 routes! Looking at the triangle above, we see that the value at the top is 3 + [the maximum of the subtree 7 and subtree 4].

This looks like a division into subproblems! If we were to cache the values of the tree at 7 and 4, we'd know the value at the top incredibly fast. The dynamic programming solution is thus as follows:

public class Main {
 /* Values at every point in the tree. */
 public static Map<Point, Integer> values;
 public static List<List<Integer>> tree;
 
 public static Integer getValue(Point p) {
  /* Check cache first. */
  if (values.containsKey(p)) {
   return values.get(p);
  }
  
  /* Boundary conditions. */
  if (p.y == tree.size() - 1) {
   return tree.get(p.y).get(p.x);
  }
  
  /* Get the values of the two subtrees. */
  Integer left = getValue(new Point(p.x, p.y + 1));
  Integer right = getValue(new Point(p.x + 1, p.y + 1));
  Integer value = tree.get(p.y).get(p.x) + Math.max(left, right);
  
  values.put(p, value);
  return value;  
 }

 public static void main(String[] args) {
  /* TODO: read tree from file. */
  
  System.out.println(getValue(new Point(0,0)));
 }

}

This solution is a sketch. I leave parsing the tree from a file as an exercise to the reader. Note that if you're serious about perfomance, using Integer and other boxed types is a bad idea. I would strongly recommend using the Trove High Performance Collections for the cache.

 Until next time!