Поиск через треугольник - PullRequest
Новая
       22

Поиск через треугольник

0 голосов
/ 21 марта 2020

Я пытался найти кратчайший путь в Pascal -подобном треугольнике с определенным «весом» в каждой точке. Это выглядит так: 

  2
 3 1
1 4 5

например. в этом случае самый короткий путь - 2-> 3-> 1 с общим «весом» 6. Вам разрешается только (смотреть сверху вниз) перемещаться в точку, расположенную на один уровень вниз вправо или влево текущей точки. Таким образом, я решил эту проблему, совершенно невозможно вычислить очень большие входные данные, такие как треугольник с 100 уровнями. Поэтому я попытался переписать весь алгоритм, основываясь на материалах, которые я нашел через inte rnet, но хорошо только на 50% - я знаю «вес» кратчайшего пути, но не знаю, какие пункты включены. Любые идеи? 

def minSumPath(A): 

    memo = [None] * len(A) 
    n = len(A) - 1

    for i in range(len(A[n])):  
    memo[i] = A[n][i]  


    for i in range(len(A) - 2, -1,-1):  
        for j in range( len(A[i])):  
            memo[j] = A[i][j] + min(memo[j], 
                                    memo[j + 1]);


    return memo[0]

РЕДАКТИРОВАТЬ Особые точки (цифры) хранятся в списке списков. Например, выше это выглядит так: [[2], [3,1], [1,4,5]]

...