Problem 015

Project Euler

Lattice paths

Problem 15

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

Using recursion and dynamic programming, a very simple solution can be derive as follow with path[][] initialized at 0 at all positions:

// using recursion and dynamic programming
countRoute(int moveDown, int moveRight)
  if moveDown == 0 or moveRight == 0 then return 1
  if path[moveDown][moveRight] == 0 then
    path[moveDown][moveRight] == countRoute(moveDown-1, moveRight) +
                                 countRoute(moveDown, moveRight-1)
  return path[moveDown][moveRight]

The solution above runs quite quickly but the complexity is O(n^2). Notice each time the routes will be either moving right (R) or down (D) and there are fixed number of such decisions (2n) must be made at each intersection which we could encode each path as a string of n R’s and n D’s in any order. Once n choices of R has been made, the choices for D’s are set. Part 3 of the overview uses combinatorial logic above to create a O(n) solution.