projecteuler 15에 대한 더 나은 솔루션이 있습니까?

Question

내 코드가 행과 열> 15에서 너무 오래 작동하는 이유는 무엇인가요? 더 좋은 해결책이 있습니까? 문제 링크 :

#!/usr/bin/env python 
rows = 3 
cols = 3 
start_row = 0 
start_col = 0 
count = 0 

def trace(row, col): 
    if row == rows and col == cols: 
     global count 
     count += 1 
     return 
    if col + 1 <= cols: 
     # print row, col 
     trace(row, col + 1) 

    if row + 1 <= rows: 
     # print row, col 
     trace(row + 1, col) 

trace(start_row, start_col) 
print count 

Answer 1

https://projecteuler.net/problem=15 결국 내가 문제를 해결할 수있는 동적 프로그래밍을 사용하여, 그것을 얻었다.

#!/usr/bin/env python 
rows = 20 
cols = 20 
pre_list = {} 

count = 0 
pre_list = {} 
for i in xrange(0, rows + 1): 
    for j in xrange(0, rows + 1): 
     pre_list[(i,j)] = [] 

for i in xrange(0, rows + 1): 
    for j in xrange(0, rows + 1): 
     if i > 0: 
      pre_list[(i,j)].append((i-1, j)) 
     if j > 0: 
      pre_list[(i,j)].append((i, j-1)) 

route = {(rows,cols):1} 

keys = route.keys() 
while True: 
    if not keys: 
     break 

    new_route = {} 
    for key in keys: 
     # print 'key', key 
     pre = pre_list[key] 
     if not pre: 
      continue 
     for item in pre: 
      new_route[item] = 1 
      # print 'route', route 
      if item in route: 
       route[item] += route[key] 
      else: 
       route[item] = route[key] 
      # print 'route', route 
     route[key] = 0 
     # print new_route 
    keys = new_route.keys() 
    # print 'new keys', keys 

print route[(0,0)]