Блог

Итак, вопрос

Учитывая сетку m x n, заполненную неотрицательными числами, найдите путь сверху слева направо снизу вправо, который минимизирует сумму всех чисел на своем пути. Вы можете двигаться только вниз и вправо.

Это распространенный вопрос интервью на собеседованиях по разработке программного обеспечения, он легко решается путем внедрения таблицы динамического программирования, чтобы определить, какой путь является наименее дорогостоящим.

Теперь мне интересно, есть ли простой способ решить альтернативную проблему? Который должен был бы найти точную сумму пути в сетке mxn.

Например, входными данными будет матрица 3×3, а целевая сумма будет, скажем, 4. Какой метод программирования следует использовать, чтобы найти путь, равный ровно 4 в нижнем правом углу от верхнего левого угла.

Ширина (или глубина) — первый поиск с обрезкой:

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

Примечание: если вам не повезло, вам все равно нужно будет просмотреть все (2N — 2)!/((N-1)! * (N-1)!) возможные пути, где N — сторона сетки. (N-1 раз вниз, N-1 раз вправо, перестановка с повторением, поскольку падения и права неотличимы в пределах их собственной категории.) Одним из таких примеров может быть сетка, в которой все пути имеют меньшую сумму, чем ваша цель.

Доказательство: предположим, что есть путь, который вы не проверяли. Если я твой враг, и я устанавливаю сетку, зная твой алгоритм. Я всегда могу настроить непроверенный путь так, чтобы он был с целевой суммой.