Разбор добавил Тимофей Гутор

Создадим матрицу предков, где будет храниться 1, если мы пришли сверху и 2, если пришли слева.
Теперь подумайте сами, как восстановить ответ.