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

Есть зданиеn этажи с лифтом, который может подниматься только на 2 этажа одновременно и на 3 этажа одновременно. Используя динамическое программирование, напишите функцию, которая будет вычислять количество шагов, которое требуется лифту, чтобы добраться от полаi на полj.

Это очевидно легко при использовании подхода с учетом состояния: вы создаете массив длиной n элементов и заполняете его значениями. Вы могли бы даже использовать технически не сохраняющий состояние подход, который включает в себя накопление результата в виде его рекурсивной передачи. Мой вопрос заключается в том, как сделать это без учета состояния, используя ленивую оценку и завязывая узел.

Я думаю, что разработал правильную математическую формулу:

гдеi+2 а такжеi-3 находятся в пределах допустимых значений.

К сожалению, я не могу заставить его прекратить. Если я поставлюi+2 сначала выберите случай, а затем выберите ровный пол, чтобы оценить четные этажи ниже целевого уровня, но это все. Я подозреваю, что он стреляет прямо на самый высокий ровный этаж для всего остального, падает на 3 уровня, затем повторяется, постоянно колебаясь между несколькими верхними этажами.

Таким образом, это, вероятно, исследование бесконечного пространства (или конечного, но с петлями) в глубине в первую очередь. Я не могу придумать, как исследовать пространство в широком смысле, не используя множество структур данных, которые эффективно имитируют подход с учетом состояния.

Хотя эта простая проблема разочаровывающе трудна, я подозреваю, что, увидев решение в 1-м измерении, я мог бы заставить его работать для 2-мерного варианта задачи.

РЕДАКТИРОВАТЬ: Многие ответы пытались решить проблему по-другому. Сама проблема мне не интересна, вопрос об используемом методе. Подход Хаосматтера к созданиюminimal Функция, которая может сравнивать потенциально бесконечные числа, возможно, является шагом в правильном направлении. К сожалению, если я попытаюсь создать список, представляющий здание с 100 этажами, результат вычислится слишком долго, поскольку решения подзадач не используются повторно.

Я предпринял попытку использовать структуру данных, ссылающуюся на себя, но она не заканчивается, происходит какой-то бесконечный цикл. Я опубликую свой код, чтобы вы могли понять, для чего я иду. Я изменю принятый ответ, если кто-то действительно сможет решить проблему, используя динамическое программирование на самореференциальной структуре данных, используя лень, чтобы избежать вычислений несколько раз.

levels = go [0..10]
  where
    go [] = []
    go (x:xs) = minimum
      [ if i == 7
          then 0
          else 1 + levels !! i
        | i <- filter (\n -> n >= 0 && n <= 10) [x+2,x-3] ]
      : go xs

Вы можете увидеть, как1 + levels !! i пытается ссылаться на ранее рассчитанный результат и какfilter (\n -> n >= 0 && n <= 10) [x+2,x-3] пытается ограничить значенияi к действительным. Как я уже сказал, это на самом деле не работает, это просто демонстрируетметод с помощью которого я хочу, чтобы эта проблема была решена. Другие способы решения этой проблемыне мне интересно.