Project Euler15 "격자 경로"

문제

2 × 2 칸의 왼쪽 상단에서 시작하면 되돌리지 않고 오른쪽 하단으로 가는 6 개의 경로가 있습니다.

그렇다면 20 x 20의 송어에서 얼마나 많은 경로가 있습니까?
ㅡㅡㅡ//오…사쿠라. 네. jp/p로지ぇc테우ぇr/그리고 x. php? cmd=레아 d&파게=P로 b㎇m% 2015

답변 정책 1

조합의 수에서도 요구되지만, 모처럼이므로 다른 알고리즘을 시험하고 싶다.
한 칸에서 목표까지의 길의 수는 해당 칸에 인접한 진행 방향의 2 칸 각각에서 골까지의 길의 수의 합과 같습니다.
→재기밖에 없다!

코드 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

답변 정책 2

웹을 조사하면, 골까지의 길의 수가 아니라, 기점으로부터의 길의 수를 for문으로 자꾸자꾸 구하는 방법이 보여졌다. 실제로 시도했지만 for 문 쪽이 훨씬 빨랐다.
조금 고찰한 바, 알고리즘으로서 당해 방식이 효율 좋을 것 같다.


모처럼이므로 대칭성도 감안해 절반만 구하도록 해봤다.

코드 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]