Как найти минимальную стоимость и путь в матрице NxN?

Question

Я должен начать с местоположения (0,0), и я могу либо двигаться вверх, либо двигаться вправо (без диагональных обходов). Мне нужна минимальная матрица затрат для достижения узла (n-1, n-1). Мне также нужен записанный путь для минимальной стоимости. Кроме того, мне нужно подсчитать общее количество путей к целевому узлу (n-1, n-1).

Для примера.

Matrix: 
7 9 2 
1 5 8 
2 3 7 

Output: 
Min cost path: 2 -> 1 -> 5 -> 8 -> 2 
Sum(Min Cost Path excluding the ending node): 16 
Total number of paths: 6 

Answer 1

Прежде всего, ваш вопрос имеет некоторые ошибки. «Я должен начать с местоположения (0,0), и я могу либо двигаться вверх, либо двигаться вправо». Я думаю, это должно быть вниз или вправо.

То, от (i,j) Вы можете перейти на: (i,j+1) и (i+1,j).

Рекурсивный формула будет

minCost(m, n) = min (minCost(m-1, n-1), minCost(m-1, n), minCost(m, n-1)) + cost[m][n] 

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

Чтобы скрыть сложность по времени, вы можете сделать это с помощью динамического программирования.

Создайте таблицу temp снизу вверх, чтобы сохранить результаты дополнительной проблемы, чтобы нам не нужно было снова вычислять. Простыми словами i,j индекс временной таблицы будет хранить путь минимальной стоимости от 0,0 до i,j. Сложность времени сводится к O(nm). Я не могу дать вам весь код, поскольку он, похоже, является вопросом домашней работы.

На ваш второй вопрос, который должен найти общие пути. Будет только один путь минимальной стоимости. Или если вы хотите найти все пути.