[PYTHON] Project Euler15 "Lattice Path"

problem

If you start from the upper left of the 2 × 2 square, there are 6 routes that go to the lower right without turning back. Then, how many routes are there in the 20 × 20 square? http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2015

Answer policy 1

The number of combinations is also required, but I want to try another algorithm because it is a big deal. The number of distances from a square to the goal is equal to the sum of the number of distances from each of the two squares in the direction of travel adjacent to the square to the goal. → There is no choice but to come back!

Code 1

def f(L,a,b):
  if not L[a][b]:
    if a == len(L)-1 or b == len(L)-1:
      L[a][b] = 1
    else:
      L[a][b] = f(L,a+1,b) + f(L,a,b+1)
  return L[a][b]

def main():
  #(x,y) = (2,2)
  (x,y) = (20,20)
  L = [[0 for i in range(0,y+1)] for j in range(i,x+1)]
  ans = f(L,0,0)
  #print ans

Answer policy 2

When I searched the web, I found a way to find the number of distances from the starting point, not the number of distances to the goal, with a for statement. I actually tried it, but the for statement was much faster. After a little consideration, this method seems to be more efficient as an algorithm.

Since it's a big deal, I tried to find only half of it in consideration of symmetry.

Code 2

def g(L,a,b):
  if a == 0:
    return 1
  elif a == b:
    return L[a-1][b]*2
  else:
    return L[a-1][b]+L[a][b-1]
  
def main2():
  seq = range(21)
  L = [[0 for i in seq] for j in seq]
  
  for a in seq:
    for b in seq[a:]:
      L[a][b] = g(L,a,b)
  #print L[20][20]