Q:

Navigating a grid

I stumbled upon a problem at Project Euler, https://projecteuler.net/problem=15
.  I solved this by combinatorics but was left wondering if there is a dynamic programming solution to this problem or these kinds of problems overall.  And say some squares of the grid are taken off - is that possible to navigate?  I am using Python.  How should I do that?  Any tips are appreciated.  Thanks in advance. 

A:

There is also a mathematical solution (which is probably what you used):
def factorial(n):
  result = 1
  for i in range(1, n + 1):
    result *= i
  return result

def paths(w, h):
  return factorial(w + h) / (factorial(w) * factorial(h))

This works because the number of paths is the same as the number of ways to choose to go right or down over w + h steps, where you go right w times, which is equal to w + h choose w, or (w + h)! / ( w! *  h!). 
With missing grid squares, I think there is a combinatoric solution, but it's very slow if there are many missing squares, so dynamic programming would probably be better there. 
For example, the following should work:
missing = [
  [0, 1],
  [0, 0],
  [0, 0],
]

def paths_helper(x, y, path_grid, missing):
  if path_grid[x][y] is not None:
    return path_grid[x][y]

  if missing[x][y]:
    path_grid[x][y] = 0
    return 0
  elif x < 0 or y < 0:
    return 0
  else:
    path_count = (paths_helper(x - 1, y, path_grid, missing) +
                  paths_helper(x, y - 1, path_grid, missing))
    path_grid[x][y] = path_count
    return path_count

def paths(missing):
  arr = [[None] * w for _ in range(h)]
  w = len(missing[0])
  h = len(missing)
  return paths_helper(w, h, arr, missing)

print paths()

