python - projecteuler 15有更好的解决方案吗？

Question

我的代码是这样的，对于rows和cols> 15来说工作时间太长了，有没有更好的解决方案？问题链接：https ://projecteuler.net/problem=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

终于明白了，使用动态规划可以解决问题。

#!/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)]