[PYTHON] Projekt Euler15 "Gitterpfad"

Problem

Wenn Sie oben links auf dem 2x2-Quadrat beginnen, gibt es 6 Routen, die rechts unten verlaufen, ohne umzukehren. Wie viele Routen gibt es dann auf dem 20 × 20-Quadrat? http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2015

Antwortrichtlinie 1

Die Anzahl der Kombinationen ist ebenfalls erforderlich, aber ich möchte einen anderen Algorithmus ausprobieren, da dies eine große Sache ist. Die Anzahl der Entfernungen von einem Quadrat zum Ziel entspricht der Summe der Anzahl der Entfernungen von jedem der beiden Quadrate in Fahrtrichtung neben dem Quadrat zum Ziel. → Es bleibt nichts anderes übrig, als zurückzukommen!

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

Antwortrichtlinie 2

Beim Durchsuchen des Webs habe ich eine Möglichkeit gefunden, die Anzahl der Pfade vom Startpunkt und nicht die Anzahl der Pfade zum Ziel mit einer for-Anweisung zu ermitteln. Ich habe es tatsächlich versucht, aber die for-Anweisung war viel schneller. Nach ein wenig Überlegung scheint diese Methode als Algorithmus effizienter zu sein.

Da es eine große Sache ist, habe ich versucht, unter Berücksichtigung der Symmetrie nur die Hälfte davon zu finden.

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]