Минимальная сумма пути, как уменьшить время выполнения

Question

Так что недавно я решил задачу Minimum Path Sum из кода leet, я придумал алгоритм со своим собственным, и он был принят. Потом я увидел, что у людей лучше время выполнения, чем у меня, но они используют один и тот же лог c. Пожалуйста, просмотрите этот код и дайте мне несколько советов, как минимизировать время выполнения.

import sys

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        t = [[0 for i in range(len(grid[0]))]for j in range(len(grid))]
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if i==0 and j==0:
                    t[i][j]= grid[i][j]
                elif(i==0):
                    t[i][j] = t[i][j-1]+grid[i][j]
                elif(j==0):
                    t[i][j] = t[i-1][j]+grid[i][j]
                else:
                    t[i][j] = min(t[i-1][j],t[i][j-1]) + grid[i][j]
        return t[-1][-1]

Answer 1

Без изменения алгоритма вы можете сделать следующее:

• Вы не используете sys, поэтому импорт не требуется.

• Инициализация списка может быть выполнена с помощью оператора *, например [0] * len(grid[0]). Это должно быть быстрее, чем понимание списка.

• Матрица t содержит много данных, к которым никогда не осуществляется доступ. В любой момент времени релевантны только последние две строки t: текущая и предыдущая строки. Таким образом, на самом деле вы можете получить пространство и выделить память только для этих двух строк, и использовать это пространство во время итерации. Более того, вы можете сделать это только с одной строкой, так как предыдущая строка необходима только для чтения значения в текущем столбце, пока вы вычисляете новое значение для текущего столбца. Таким образом, вы можете просто постепенно перезаписывать значения в одной строке вместо использования двух строк.

• Особый случай для j==0 можно упростить, добавив префикс вышеупомянутой строки с одним дополнительная ценность Бесконечность. Таким образом, вы можете сделать так, что для j==0 особый случай больше не нужен. Это потому, что min(x, Infinity) всегда будет x .

• Аналогичный трюк может быть применен для случая i==0: просто инициализируйте вышеупомянутую строку с бесконечностью ценности. Затем установите начальное значение пути-суммы в этой строке. Поэтому, когда вы обрабатываете первую строку сетки, функция min будет правильно накапливать и суммировать значения слева направо, что вам и нужно, когда i==0.

• Use enumerate в ваших циклах: таким образом вы получаете индекс и значение сетки одновременно.

Вот как может выглядеть код после внесения этих изменений:

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        # You only need a row for this dynamic programming, not a matrix.
        # The first value is an extra Infinity value to make the `j==0`
        #    case just like any other.
        t = [float('inf')] * (len(grid[0]) + 1)
        t[1] = 0  # At the start we have a path-sum of zero
        for row in grid:
            for j, val in enumerate(row):
                # Updates are made from index 1 onwards. 
                # At index 0 we have a static Infinity.
                # t[j+1] is the sum for the path coming from above, and
                # t[j] is the sum for the path coming from the left.
                t[j+1] = min(t[j+1], t[j]) + val
        return t[-1]