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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s