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

Учитывая целое число N и три матрицы N x N X[][] , Y[][] и Z[][] , задача состоит в том, чтобы вычислить минимальную стоимость, необходимую для достижения правого нижнего угла из левого верхнего угла матрицы. используя следующие движения:

• Переместитесь в ячейку в правильном направлении от (i, j), что будет стоить X[i][j] .
• Переместитесь в ячейку в направлении вниз от (i, j), что будет стоить Y[i][j] .
• Переместитесь в ячейку по диагонали от (i, j), которая будет стоить Z[i][j] ,

Пример:

Input: N = 3, X[][] = {{1, 2, 1}, {3, 4, 5}, {1, 1, 1}}, Y[][] = {{2, 3, 4}, {1, 3, 1}, {2, 1, 1}}, Z[][] = {{1, 8, 9}, {1, 4, 5}, {6, 5, 4}}.
Output: 4
Explanation: The path which will lead to the minimum cost is as follows: 

• In first move, move downwards from (0, 0) to (1, 0) which will add a cost of 2.
• In second move, move diagonally from (1, 0) to (2, 1) which will add a cost of 1.
• In third and final move, move to the right from (2, 1) to (2, 2) which will add a cost of 1.

Therefore, the total required cost is 4, which is the minimum possible.

Input: N = 2, X[][] = {{1, 1}, {1, 1}}, Y[][] = {{1, 1}, {1, 1}}, Z[][] = {{1, 1}, {1, 1}}
Output: 1

Подход: Данная проблема имеет структуру, аналогичную стандартной задаче о пути минимальной стоимости. Ее можно решить с помощью динамического программирования. Путь к (i, j) должен проходить через одну из 3 ячеек: (i-1, j-1) или (i-1, j) или (i, j-1) . Таким образом, минимальную стоимость достижения (i, j) можно записать в виде следующего соотношения:

minCost(i, j) = min ( minCost(i, j – 1) + X[i][j – 1],  
                                    minCost(i – 1, j) + Y[i – 1][j], 
                                    minCost(i – 1, j – 1) + Z[i – 1][j – 1])

Поэтому создайте двумерный массив dp[][] , где dp[i – 1][j – 1] хранит минимальную стоимость достижения ячейки (i, j) из (0, 0) и заполните dp[][ ] массив снизу вверх. Значение, хранящееся в dp[N – 1][N – 1] , является требуемым ответом.

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

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