Динамическое программирование для двух последовательных вопросов, советы по перемещению индексов

Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания

Сегодня 37-я статья LeetCode, мы продолжаем радостно чистить вопросы. Вопросы, которые нужно решить сегодня, выводят LeetCode 63 и 64, которые представляют собой уникальные пути II и минимальную сумму пути.

Из названия темы мы видим, что все сегодняшние темы связаны с путем. На самом деле, не только это, но и значения этих двух вопросов почти одинаковы. По сути, они являются расширением и расширением вопроса LeetCode 62. упоминалось в предыдущей статье. Вот почему мы объединили эти два вопроса.

Unique Paths II

Давайте сначала посмотрим на первый вопрос, Уникальные Пути II. Это в основном то же самое, что и 62 вопроса, и это задача, в которой робот проходит прямоугольный лабиринт, чтобы решить общее количество путей. Вероятно, как на картинке ниже, робот начинает с верхнего левого угла и продвигается к нижнему правому углу.

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

Образец

Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Как видно из примера, заголовок использует двумерный массив для представления прямоугольника, а точка 1 в массиве представляет блокпост.

Если вы читали нашу предыдущую статью и ответили на вопрос LeetCode 62, вы обнаружите, что этот вопрос является почти такой же версией, и даже идеи решения проблем такие же. Если вы этого не сделали, вы можете просмотреть его через портал ниже:

LeetCode 62: Думаете, динамическое программирование непобедимо? Есть лучшее решение этой проблемы

Применим идею 62 вопросов, из которых полностью применимо решение динамического программирования. Наличие блокпоста влияет только на точку самого блокпоста и точки рядом с ним, на которые можно перенестись, для себя он недостижим, а количество естественно доступных путей равно 0. А для точки, в которую он переходит, эта точка недоступна и естественный вклад также равен 0. Поэтому нам нужно только установить положение контрольно-пропускного пункта на 0 во время процесса передачи.

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

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

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        n, m = len(obstacleGrid), len(obstacleGrid[0])
        # 我们维护的下标i从1到n，j从1到m
        dp = [[0 for _ in range(m+2)] for _ in range(n+2)]
        
        dp[0][1] = 1
        for i in range(1, n+1):
            for j in range(1, m+1):
               # 判断当前位置是否可达，由于下标范围不一致，所以要-1
                if obstacleGrid[i-1][j-1] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[n][m]

Этот вопрос выглядит просто. Не так просто сразу написать код правильно. Есть яма, что диапазон индексов, поддерживаемый нашим массивом dp, отличается от индекса массива дорожных блоков, заданного заголовком. Мы устанавливаем индекс из 1 для начала, так что вам не нужно учитывать проблему выхода за пределы массива при передаче. Поскольку значение нижнего индекса начинается с 1, когда мы оцениваем, является ли соответствующая позиция блокпостом, нам нужно, чтобы i и j были равны -1.

Перейдем к следующему вопросу.

Minimum Path Sum

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

Образец

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

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

Для каждой точки i,j у него есть два источника, i-1,j и i,j-1. Уравнение перехода состояния. Массив стоимостей здесь представляет собой стоимость каждого очка, указанного в заголовке.

Давайте посмотрим непосредственно на код:

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if n == 0:
            return 0
        m = len(grid[0])
        
        # 同样，我们dp维护的下标从1开始，初始化时赋值成无穷大
        dp = [[0x3f3f3f3f for _ in range(m+2)] for _ in range(n+2)]
        
        # 将0，1位置赋值成0，给(1, 1)提供一个消耗为0的入口
        dp[0][1] = 0
        
        for i in range(1, n+1):
            for j in range(1, m+1):
               # 由于下标从1开始，不用担心越界，无脑转移即可
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1]
        
        return dp[n][m]

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

конец

На этом два вопроса о LeetCode 63 и 64 закончены.

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

Сегодняшняя статья здесь, оригинальность не из легких,Отсканируйте код, чтобы подписаться на менядля более замечательных статей.