Восстановление ответа: через массив динамики и через массив предков.

Восстановление ответа

Теперь мы умеем находить ответ в задачах на ДП, но в некоторых задачах нам также интересно как мы можем его получить, например в задаче про черепашку нам может быть интересен путь. Такую задачу называют восстановлением ответа в динамике.

Есть два способа, которыми можно это сделать.

1) Хранить в массив prev откуда ты пришел в эту клетку.

Когда мы выбираем максимум из левой и верхней клетки, мы на самом деле решаем, какой последний ход будет в оптимальном пути до этой клетки - сверху или слева, и берем ответ для той клетки, сложнный с монетами в этой клетке. Давайте координаты клетки, откуда мы пришли, хранить в массиве prev. Или, в данном случае, можно хранить не координаты а просто 1, если пришли слева, и 0, если пришли сверху.