Максимальная стоимость достижения самой нижней строки из верхнего левого и верхнего правого углов заданной матрицы

Дана матричная сетка [][] размера M * N , где каждая ячейка матрицы обозначает стоимость, которая должна присутствовать в этой ячейке. Задача состоит в том, чтобы максимизировать стоимость перехода в самую нижнюю строку из верхнего левого и верхнего правого угла матрицы, где на каждом шаге:

• Из клетки (i, j) может быть движение в (i+1, j-1) , (i+1, j) или (i+1, j+1) .
• Если обе точки одновременно находятся в одной ячейке, стоимость ячейки будет добавлена только для одной.
• Ни в коем случае точки не могут выйти за пределы сетки.

Примеры:

Input: 
grid = {{3, 1, 1}, 
            {2, 5, 1}, 
            {1, 5, 5}, 
            {2, 1, 1}}
Output: 24
Explanation: Path from top-left and top-right are described in color orange and blue respectively.
Cost for first path is (3 + 2 + 5 + 2) = 12.
Cost for second path is (1 + 5 + 5 + 1) = 12.
Total cost is 12 + 12 = 24.

Ex1 – Visual Grid

Input:
grid = {{1, 0, 0, 0, 0, 0, 1}, 
            {2, 0, 0, 0, 0, 3, 0}, 
            {2, 0, 9, 0, 0, 0, 0}, 
            {0, 3, 0, 5, 4, 0, 0}, 
            {1, 0, 2, 3, 0, 0, 6}}
Output: 28
Explanation: Path from top-left and top-right are described in color orange and blue respectively.
Cost of the first path is (1 + 9 + 5 + 2) = 17.
Cost of the second path is (1 + 3 + 4 + 3) = 11.
Total cost of the paths is 17 + 11 = 28.
This is the maximum cost possible.

Ex2 – Visual Grid

Интуиция: обозначьте точку в верхнем левом углу как point1 и в верхнем правом углу как point2 . Далее следует интуиция, стоящая за решением проблемы.

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

Can point1 be moved firstly to the bottom row, and then point2?

Maybe not. In this case, the movement of point1 will impact the movement of point2. In other words, the optimal track of point2 depends on the track of point1. In this case there will be requirement to record the whole track of point1 as the state for point2 in DP. The number of sub-problems is too much.

In fact, in any case, when anyone point is moved several steps earlier than the other, the movement of the first point will impact the movement of the other point. So both the points should be moved synchronously.

• Задайте состояние DP как (row1, col1, row2, col2) , где (row1, col1) представляет местоположение point1 , а (row2, col2) представляет местоположение point2 . Если они перемещаются синхронно, обе точки всегда будут в одной строке. Следовательно, строка1 = строка2 .
  Пусть строка = строка1 = строка2 . Состояние DP упрощается до (row, col1, col2) , где (row, col1) представляет местоположение point1 , а (row, col2) представляет местоположение point2 .
• Итак, для функции DP: Пусть dp(row, col1, col2) возвращает максимальную стоимость, если point1 начинается с (row, col1) и point2 начинается с (row, col2) .
• Базовые случаи заключаются в том, что обе точки начинаются в нижней строке. В этом случае не нужно двигаться, просто считается стоимость в текущих ячейках. Помните, что нельзя делать двойной подсчет, если точки находятся в одной и той же ячейке.
• В остальных случаях добавляйте максимальную стоимость путей в будущем. Здесь идет функция перехода. Так как точки могут двигаться синхронно, и каждая точка совершает три разных движения за один шаг, то всего 3*3 = 9 возможных движений для двух роботов:

• Максимальная стоимость путей в будущем будет максимальной из этих 9 перемещений, что является максимальным
  dp(row+1, new_col1, new_col2) , где new_col1 может быть col1 , col1+1 или col1-1 , а new_col2 может быть col2 , col2+1 или col2-1 .

Подход 1 — динамическое программирование (снизу вверх): решение проблемы основано на концепции динамического программирования и использует вышеописанную интуицию.

• Определите функцию dp , которая принимает на вход три целых числа row, col1 и col2 .
  • (строка, столбец1) представляет местоположение точки1 , а (строка, столбец2) представляет местоположение точки2 .
  • Функция dp возвращает максимальную стоимость, если точка 1 начинается с (строка, столбец1), а точка 2 начинается с (строка, столбец2) .
• В функции дп :
  • Добавьте стоимость в (row, col1) и (row, col2) . Не считайте дважды, если col1 = col2 .
  • Если последняя строка не достигнута, добавьте максимальную стоимость, которую можно получить в будущем пути.
  • Максимальная стоимость, которая может быть достигнута в будущем, равна максимуму dp(row+1, new_col1, new_col2) , где new_col1 может быть col1, col1+1 или col1-1 , а new_col2 может быть col2, col2+1, или столбец2-1 .
  • Верните полную стоимость.
• Наконец, верните dp(row=0, col1=0, col2=last_column) в основную функцию.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(M * N ² )
Вспомогательное пространство: O(M * N ² )

Подход 2 — динамическое программирование (сверху вниз): это решение также основано на подходе динамического программирования, использующем упомянутую выше интуицию. Разница лишь в том, что здесь используется нисходящий подход .

• Определите трехмерный массив dp , где каждое измерение имеет размер M, N и N соответственно, аналогично подходу 1.
• Здесь dp[row][col1][col2] представляет максимальную стоимость при достижении точки 1 в позиции (row, col1) и точки 2 в позиции (row, col2) .
• Чтобы вычислить dp[row][col1][col2] (уравнение перехода):
  • Добавьте стоимость в (строка, столбец1) и (строка, столбец2). Не считайте дважды, если col1 = col2.
  • Если не в первой строке, добавьте максимальную стоимость уже пройденного пути.
• Наконец, верните максимальное значение из последней строки.

Примечание. Для сохранения первого измерения можно использовать сжатие состояния: dp[col1][col2] . Просто повторно используйте массив dp после повторения одной строки.

Реализация 1: без сжатия состояния

Временная сложность: O(M * N ² )
Вспомогательное пространство: O(M * N ² )

Реализация 2: со сжатием состояния

Временная сложность: O(M * N ² )
Вспомогательное пространство: O(N ² )