Как улучшить эту рекурсивную функцию?

Question

Как улучшить эту рекурсивную функцию, потому что она слишком медленная. Эта проблема взята из Project Euler .

Задача:

Начиная с верхнего левого угла сетки 2 × 2, и только имея возможность двигаться вправо и вниз, в правом нижнем углу есть ровно 6 маршрутов.

Сколько таких маршрутов проходит через сетку 20 × 20?

MAX = 2
paths = 0

def a(x=0,y=0):
    if x==MAX and y==MAX:
        global paths
        paths+=1
        return
    if x>MAX or y>MAX:
        return
    a(x+1,y)
    a(x,y+1)
a()
print(paths)

Он проверяет все вниз и вправо, пока не достигнет последней ячейки в сетке. Если он перекрывает сетку, он остановится и перейдет к следующей функции в стеке вызовов

Answer 1

Эта проблема является идеальным кандидатом для применения принципов динамического программирования c с использованием мемоизации, поскольку она содержит перекрывающихся подзадач и оптимальных подструктур. Ваше рекурсивное решение занимает много времени время, потому что он тратит большую часть своего времени на решение одной и той же проблемы снова и снова.

Использование:

def find_paths(start, end, memo):
    if start == end:
        return 1
    elif start[0] > end[0] or start[1] > end[1]:
        return 0

    r_point, b_point = (start[0] + 1, start[1]), (start[0], start[1] + 1) 
    if not r_point in memo:
        memo[r_point] = find_paths(r_point, end, memo)

    if not b_point in memo:
        memo[b_point] = find_paths(b_point, end, memo)

    return memo[r_point] + memo[b_point]

Вызов функции:

print(find_paths((0, 0), (2, 2), {}))
print(find_paths((0, 0), (20, 20), {}))
print(find_paths((0, 0), (100, 100), {}))

Это отпечатки:

6
137846528820
90548514656103281165404177077484163874504589675413336841320

Answer 2

Это похоже на треугольник Pascal. Чтобы добраться до каждой точки на сетке, требуется сумма путей по позициям выше и влево до главной диагонали (прогрессия Pascal), а затем вниз до места назначения.

2x2

Pascal's   Rest
*--1--1    *--1--1
|  |  |    |  |  |
1--2--+    1--2--3
|  |  |    |  |  | 
1--+--+    1--3--6  ==> 6 paths

3x3

Pascal's      Rest
*--1--1--1    *--1--1--1 
|  |  |  |    |  |  |  |
1--2--3--+    1--2--3--4
|  |  |  |    |  |  |  |
1--3--+--+    1--3--6--10
|  |  |  |    |  |  |  |
1--+--+--+    1--4--10-20 ==> 20 paths

4x4

Pascal's       rest        
*--1--1--1--1  *--1--1--1--1
|  |  |  |  |  |  |  |  |  |
1--2--3--4--+  1--2--3--4--5
|  |  |  |  |  |  |  |  |  |
1--3--6--+--+  1--3--6--10-15 
|  |  |  |  |  |  |  |  |  |
1--4--+--+--+  1--4--10-20-35 
|  |  |  |  |  |  |  |  |  |
1--+--+--+--+  1--5--15-35-70 ==> 70 paths

На этом этапе вы можете сделать больше математики или реализовать эффективный алгоритм для вычисления результата:

N = 4
paths = [1]
for _ in range(N):
    paths = [ a+b for a,b in zip(paths,[0]+paths) ]+[1] # Pascal's
for _ in range(N):
    paths = [ a+b for a,b in zip(paths,paths[1:]) ]     # Rest
result = paths[0]

More Math : если вы расширите квадрат до 2N, вы также заметите, что результатом является точка, находящаяся точно посередине основной диагональ. Это N-е значение в строке 2N треугольника Pascal.

*--1--1--1--1··1··1··1··1  
|  |  |  |  |  :  :  :
1--2--3--4--5··+··+··8·· 
|  |  |  |  |  :  :
1--3--6--10-15·+··28··   
|  |  |  |  |  :
1--4--10-20-35·56·· 
|  |  |  |  |  
1--5--15-35-70··   <-- 70 is combinations of 4 in 8 
:  :  :  :    
1··+··+··56··
:  :  :    
1··+··28··
:  :    
1··8··
:   
1··

В соответствии со свойствами треугольника Pascal, это эквивалентно количеству комбинаций значений N в наборе 2N.

Может быть рассчитано как ( 2н)! / N! ^ 2: factorial(2*N)//factorial(N)**2

N=2 --> 4!/2!^2 --> 24/4 --> 6

N=3 --> 6!/3!^2 --> 720/36 --> 20

N=4 --> 8!/4!^2 --> 40320/576 --> 70

...

N=20 --> you do the math :)

Answer 3

Существует простое математическое решение.

Нам нужно сделать ровно 20 ходов вниз, на любую из 40 позиций, которые у нас есть (как всегда, 20 вниз + 20 вправо)

Поэтому ответ 40 Выберите 20 = 137846528820

Подробнее о проблеме здесь