минимальная сумма L в матрице mxn - 2

Question

Вот мой первый вопрос о максимальной сумме L, а вот другая и сложная версия.

Проблема: Учитывая mxn положительный целочисленная матрица находит минимальную сумму L от 1-й строки до м-й строки .L (4 предмета) любит ход шахматной лошади

Пример: M = 3x3

0 1 2

1 3 2

4 2 1

Возможные ходы L: (0 1 2 2), (0 1 3 2) (0 1 4 2) Мы должны перейти от строки 1th к строке 3th сминимальная сумма

Я решил это с помощью динамического программирования, и вот мой алгоритм:

1. Возьмите mxn другой массив Minimum L Moves Sum и скопируйте первую строкуОсновная матрица.Я называю это (MLMS) 2. , начиная с первой ячейки, и просматриваю движения L вверх и вычисляю 3. вставить его в MLMS, если оно меньше существующего значения 4. Делать шаг 2. до м * строки 5. Выберите минимальную сумму в m'th строке

Позвольте мне объяснить на моем примере шаг за шагом:

1. M [0] [0] сумма (L1 = (0, 1, 2, 2)) = 5;сумма (L2 = (0,1,3,2)) = 6;поэтому MLMS [0] [1] = 6сумма (L3 = (0, 1, 3, 2)) = 6;сумма (L4 = (0,1,4,2)) = 7;поэтому MLMS [2] [1] = 6

2. M [0] [1] сумма (L5 = (1, 0, 1, 4)) = 6;сумма (L6 = (1,3,2,4)) = 10;поэтому MLMS [2] [2] = 6

   ... последний MSLS:0 1 24 3 66 6 6Это означает, что 6 - это минимальная сумма L, которую можно достичь от 0 до м.

Я думаю, что это O (8 * (м-1) n) = O (м н) .Есть ли оптимальное решение или алгоритмы динамического программирования подходят для этой проблемы?

Спасибо, простите за длинный вопрос

Answer 1

Как может быть и 0-th, и m-th строк в матрице с общим количеством m строк?

В любом случае, простой Dijkstra даст вам оптимальный путь в O(n*m) (при условии, что у вас есть хорошая структура данных, чтобы найти минимум в списке еще не достигнутых точек).

Кроме того, если ваш рыцарь может двигаться только вниз по доске (иногда полезно подняться вверх, чтобы уменьшить общий вес пути), вы можете написать простое DP. Просто начните с нижней части доски и для каждой позиции рассчитайте, сколько потребуется, чтобы достичь дна. Поскольку вы можете сделать до 4 ходов из каждой позиции, это простая проверка на минимум. Как то так

for (int row = m - 1; row >= 0; --row) {
    for (int col = 0; col < m; ++col) {
        int path1 = a[row][col + 1] + a[row][col + 2] + a[row + 1][col + 2] + best[row + 1][col + 2];
        int path2 = a[row][col + 1] + a[row + 1][col + 1] + a[row + 2][col + 1] + best[row + 2][col + 1];
        int path3 = ...
        int path4 = ...
        best[row][col] = min(path1, path2, path3, path4);
    }
}

редактировать
Зачем вам нужно идти вверх? Представьте себе такую ​​матрицу (где * означает какое-то смехотворно большое число, например, 1000000000). Очевидно, что вам придется пройти от (0, 0) до правой части доски, прежде чем идти вниз.

111111111111
111111111111
*********111
*********111

Итак, путь будет выглядеть так

...1...1...1
11...1...1..
*********11.
*********11.