У меня есть жадное решение для следующей проблемы.Я хочу знать, как это доказать?
Проблема заключается в следующем: Учитывая n x n 2D матрицу неотрицательных целых чисел, найдите три такие ячейкичто сумма этих ячеек и соседних ячеек максимальноЕсли две выбранные ячейки имеют общие соседние ячейки, соседние ячейки участвуют в сумме только один раз, а две ячейки считаются смежными, если они имеют общее ребро.
Наивные грубые решения работают в O (n 6 ) .Я написал жадное решение, которое работает в O (n 4 ) .Жадное решение использует эту идею, что ячейка с максимальной общей суммой себя и соседних ячеек всегда является частью ответа.Я протестировал оба решения на нескольких тестовых примерах, и результаты идентичны.
В жадном алгоритме сначала я выбираю ячейку с максимальной общей суммой себя и соседних ячеек, а затем перебираю все возможные пары ячеек.
Теперь мой вопрос таков: почему эта жадная стратегия работает?Я хочу доказательства.Спасибо!