Несколько лет назад я прошел курс алгоритмов, где мы давали следующую задачу (или такую):

Есть здание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