Блог

У вас есть NxN сетка, содержащая набор положительных и отрицательных чисел, и вы должны найти оптимальный путь через нее. Путь должен проходить ровно через одну ячейку в каждой строке, а его ячейки в соседних строках должны быть соединены либо вертикально, либо по диагонали. Можете ли вы найти алгоритм для решения этой задачи без оценки каждой перестановки?

Я предполагаю, что «оптимальный путь» определяется как путь с наибольшей суммой?

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

 solution[i][j] = grid[i][j]   max(solution[i-1][j], solution[i-1][j-1], solution[i-1][j 1]) 
  

принимая во внимание граничные условия, конечно. Начальные условия были бы:

 solution[0][j] = grid[0][j]
  

Вам также необходимо отслеживать фактический пройденный путь (какие элементы сетки выбраны) по оптимальному пути. Как только вы доберетесь до последней строки, пройдите по строке и найдите максимальное значение. Это даст вам оптимальный путь, а также его значение.