Динамическое программирование с чрезвычайно большими входами

Question

Проблема заключается в том, чтобы найти путь с минимальным количеством шагов, необходимых для достижения (m, n) из (1, 1) (если он существует) при условии, что вы можете перемещаться только двумя способами : (x, y) = (x + y, y) или (x, y) = (x, x + y).

Я попытался сделать это с помощью динамического программирования, но m и n могут быть до 10^25, поэтому это невозможно. Как я могу адаптировать свое решение так, чтобы он мог работать на больших входах? Или есть альтернативный метод?

Answer 1

Вернитесь назад. Скажите, что ваша цель (x, y). Если x> y, то последний шаг должен был быть от (x - y, y); в противном случае последний шаг должен был быть от (x, y - x). (Если x = y, это место недоступно.) Работая в обратном направлении, легко видеть, что есть только один способ достичь любого доступного местоположения цели, и этот путь всегда очевиден.

Учитывая это, вы можете использовать незначительные изменения на Euclidean algorithm для решения этой проблемы. Каждый итерационный или рекурсивный уровень представляет собой несколько шагов в данном направлении, и вы можете отслеживать количество шагов, которые вам понадобятся на этом пути.