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

По заданной матрице mat[][] размерности N * M и набору координат ячеек [][] размера Q задача состоит в том, чтобы найти максимальную сумму пути из верхней левой ячейки (1, 1 ) в нижнюю правую ячейку (N, M) , так что путь должен содержать хотя бы одну из координат из массива координат[][2] . Из любой ячейки (i, j) матрицы разрешены только ходы (i + 1, j) или (i, j + 1) .

Примеры:

Input: mat[][  = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}, coordinates[][] = {{1, 2}, {2, 2}}
Output: 27
Explanation:
The path having the maximum is given by:
(1, 1) -> (2, 1) -> (2, 2) -> (3, 2) -> (3, 3).
The above path passes through the coordinates (2, 2). Therefore, the sum of the path is given by (1 + 4 + 5 + 8 + 9) = 27, which is maximum path.

Input: mat[][] = {{1, 3}, {6, 7}, {8, 9}} , coordinates[][2] = {{1, 1}}
Output: 24
 

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

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

Эффективный подход. Описанный выше подход также можно оптимизировать с помощью динамического программирования. Рассмотрим две матрицы start[][] и end[][] такие, что start[i][j] обозначает максимальную сумму путей из ячейки (1, 1) в ячейку (i, j) и end[i] [j] обозначает максимальную сумму путей из ячейки (i, j) в ячейку (N, M) . Следовательно, для любой координаты (X, Y) максимальная сумма пути может быть рассчитана как:

start[X][Y] + end[X][Y] – mat[X][Y]

Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте две матрицы, скажем, start[][] и end[][] размерностей N*M так, чтобы start[i][j] обозначал максимальную сумму путей из ячейки (1, 1) в ячейку (i, j ) и end[i][j] обозначает максимальную сумму путей из ячейки (i, j) в ячейку (N, M) .
• Инициализируйте переменную, скажем, как INT_MIN , которая хранит результирующую максимальную сумму.
• Вычислите максимальную сумму пути от ячейки (1, 1) до каждой ячейки (i, j), используя подход «снизу вверх», обсуждаемый в этой статье, и сохраните ее в матрице start[][] .
• Вычислите максимальную сумму путей от ячейки (N, M) до каждой ячейки (i, j), используя нисходящий подход, обсуждаемый в этой статье, и сохраните ее в матрице end[][] .
• Перейдите координаты массива[][] и для каждой координаты (X, Y) обновите значение ans как максимальное значение ans and (start[X][Y] + end[X][Y] – mat[X][ Й]) .
• После выполнения вышеуказанных шагов выведите значение ans как результирующую максимальную сумму.

Ниже приведена реализация вышеуказанного подхода:

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