Метод восстановления пути с помощью массива предшественников
Алгоритм восстановления ответа в задачах про оптимальный маршрут можно кратко описать таким образом.
-
Создайте дополнительный массив prev длиной N, в котором каждый элемент prev[i] будет хранить индекс предыдущей точки на маршруте.
-
Во время вычисления dp (массив, которых хранит значения на каждом шаге), когда обновляете значение dp[i], также обновите prev[i] на индекс точки, от которой пришли в i.
-
После завершения вычислений маршрута наименьшей стоимости будет можно восстановить, начиная с конечной точки N-1 и двигаясь в обратном направлении, используя информацию из массива prev.