Головоломка - nXn сетка из + ve, -ve целых чисел.Найти оптимальный путь через него

Question

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

Answer 1

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

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

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]

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