Уникальные пути II, задача динамического программирования, время O (n ^ 2), пространство O (n ^ 2)

Это основано на этом leetcode вопрос. Я получил правильный ответ, но я знаю, что он мог бы быть намного чище. Я также знаю, что должно быть пространственное решение O (n), но я не уверен, как его реализовать чисто.

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

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        #initialize memoization array
        memo = [[-1 for i in range(len(obstacleGrid[0]))] for j in range(len(obstacleGrid))]


        #add known values before any calculation (last row and last column)
        memo[len(memo)-1][len(memo[0])-1] = 1
        for i in range(len(memo[0])-2,-1,-1):
            if obstacleGrid[len(memo)-1][i] != 1:
                memo[len(memo)-1][i] = memo[len(memo)-1][i+1]
            else:
                memo[len(memo)-1][i] = 0 
        
        for j in range(len(memo)-2,-1,-1):
            if obstacleGrid[j][len(memo[0])-1] != 1:
                memo[j][len(memo[0])-1] = memo[j+1][len(memo[0])-1]
            else:
                memo[j][len(memo[0])-1] = 0
        
        if obstacleGrid[len(memo)-1][len(memo[0])-1] == 1:
            return 0 
        
        #does calculations
        def helper(row,col):
            nonlocal memo
            if obstacleGrid[row][col] == 1:
                return 0 
            if memo[row][col] == -1:
                memo[row][col] = helper(row+1,col) + helper(row,col+1)
            return memo[row][col]
        
        return helper(0,0)
            

Хорошее решение, несколько предложений:

• Дублированный код: функции len(memo) а также len(memo[0]) вызываются несколько раз. При работе с матрицей принято называть m количество строк (len(memo)) а также n количество столбцов (len(memo[0])). Это может помочь уменьшить дублирование кода. Как отметил @Manuel в комментариях, m а также n также определены в описании проблемы.

• Последний элемент списка: вместо memo[len(memo)-1] ты можешь использовать memo[-1].

• Проверка ввода: эта проверка ввода:

  if obstacleGrid[len(memo)-1][len(memo[0])-1] == 1:
      return 0 
  

  выполняется слишком поздно в коде, после memo матрица полностью построена. Лучше переместить его вверх в начале функции. Кстати, с предыдущим предложением его можно сократить до:

  if obstacleGrid[-1][-1] == 1:
      return 0
  

• Именование: строка называется row во вспомогательной функции и j в остальной части кода. То же самое для колонки. Используйте одно и то же имя, чтобы быть последовательным.

• Переменные выбрасывания: при инициализации памятки:

  memo = [[-1 for i in range(len(obstacleGrid[0]))] for j in range(len(obstacleGrid))]
  

  переменные i а также j не используются. Их можно заменить на _.

• Подсказки по типу: the helper функция отсутствует подсказка типа.

• Кеш LRU: есть удобная аннотация, которая автоматически запоминает, @lru_cache. Или безграничный @cache в Python 3.9.

Пример использования @lru_cache:

def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
    m = len(obstacleGrid)
    n = len(obstacleGrid[0])

    if obstacleGrid[-1][-1] == 1:
        return 0

    @lru_cache(maxsize=None)
    def helper(row: int, col: int) -> int:
        if row == m - 1 and col == n - 1:
            return 1
        if row < m and col < n:
            if obstacleGrid[row][col] == 1:
                return 0
            return helper(row + 1, col) + helper(row, col + 1)
        return 0

    return helper(0, 0)

Для решений динамического программирования, вы можете взглянуть на «Решение» раздел или «Обсуждение» раздел используя теги python а также dynamic programming.

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

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

def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
    paths = [1] + [0] * (len(obstacleGrid[0]) - 1)
    for row in obstacleGrid:
        for j, obstacle in enumerate(row):
            if j:
                paths[j] += paths[j - 1]
            if obstacle:
                paths[j] = 0
    return paths[-1]

Кстати, ты нет O (n ^ 2), но O (mn).