Лениво связывая узел для 1-мерного динамического программирования
Несколько лет назад я прошел курс алгоритмов, где мы давали следующую задачу (или такую):
Есть зданиеn
этажи с лифтом, который может подниматься только на 2 этажа одновременно и на 3 этажа одновременно. Используя динамическое программирование, напишите функцию, которая будет вычислять количество шагов, которое требуется лифту, чтобы добраться от полаi
на пол.j
Это очевидно легко при использовании подхода с учетом состояния: вы создаете массив длиной n элементов и заполняете его значениями. Вы могли бы даже использовать технически не сохраняющий состояние подход, который включает в себя накопление результата в виде его рекурсивной передачи. Мой вопрос заключается в том, как сделать это без учета состояния, используя ленивую оценку и завязывая узел.
Я думаю я'Мы разработали правильную математическую формулу:
гдеi+2
а такжеi-3
находятся в пределах допустимых значений.
К сожалению, я не могуне заставить его прекратить. Если я поставлюi+2
сначала выберите случай, а затем выберите ровный пол, чтобы оценить четные этажи ниже целевого уровня, но этосидеть. Я подозреваю, что он стреляет прямо на самый высокий ровный этаж для всего остального, падает на 3 уровня, затем повторяется, постоянно колебаясь между несколькими верхними этажами.
Так что's, вероятно, исследуя бесконечное пространство (или конечное, но с петлями) в глубине первым способом. Я могу'не думайте о том, как исследовать пространство в широком смысле, не используя большое количество структур данных между ними, которые эффективно имитируют подход с учетом состояния.
Хотя эта простая проблема разочаровывающе трудна, я подозреваю, что, увидев решение в 1-м измерении, я мог бы заставить его работать для 2-мерного варианта задачи.
РЕДАКТИРОВАТЬ: Многие ответы пытались решить проблему по-другому. Сама проблема неМне интересно, вопрос об используемом методе. Chaosmatter»подход к созданиюminimal
Функция, которая может сравнивать потенциально бесконечные числа, возможно, является шагом в правильном направлении. К сожалению, если я попытаюсь создать список, представляющий здание с 100 этажами, результат вычислится слишком долго, поскольку решения подзадач не используются повторно.
Я предпринял попытку использовать структуру данных, ссылающуюся на себя, но она неt завершается, происходит какой-то бесконечный цикл. Я'Я опубликую свой код, чтобы вы могли понять, что яЯ иду за. Я'Я изменю принятый ответ, если кто-то действительно сможет решить проблему, используя динамическое программирование на самореференциальной структуре данных, используя лень, чтобы избежать вычислений более одного раза.
levels = go [0..10]
where
go [] = []
go (x:xs) = minimum
[ if i == 7
then 0
else 1 + levels !! i
| i n >= 0 && n n >= 0 && n