Подсчитать количество возможных путей преодоления препятствий, чтобы добраться до места назначения?

Question

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

Пример:

{0, 15, 20, 25, 29, 31, ......, 45}

В указанном выше массиве '0' - начальная позиция;«45» - конечное местоположение;а все остальное посередине - это точки пути на разных расстояниях (15, 20, 25, 29, 31 и т. д.).Есть препятствия между последовательными путевыми точками.Предположим, что массив всегда сортируется в порядке возрастания от начального до конечного местоположения.Как я могу рассчитать все возможные способы достижения конечного местоположения с различными перестановками прыжков через препятствия (каждый прыжок в пределах максимального размера прыжка)?

Answer 1

Это можно решить с помощью динамического программирования или DFS (глубина, а не ширина), в зависимости от того, как вы смотрите на проблему.В любом случае, вы собираетесь запоминать решение от каждой точки пути до конца.Вы можете работать с любого конца;проблема полностью обратима.Давайте рассмотрим последовательность {0, 8, 9, 15, 20} и размер прыжка 10.

Starting from 0, you can reach nodes 8 and 9.  You'll recur on each of those.
From 8, you can reach 9 and 15; you'll recur on each.
From 9, you can reach only 15.
From 15, you can reach only 20.

Восхождение на дерево повторений:

There's 1 way to get to the end from 20 (vapid result), so f(20) = 1
From 15, there's one way to reach the end: through 20, so f(15) = 1
From 9, there's one way to reach the end: through 15, so f(9) = 1
From 8, you have two choices: 9 and 15.  f(8) = f(9) + f(15) = 1 + 1 = 2
From 0, you have two choices: 8 and 9.  f(0) = f(8) + f(9) = 2 + 1 = 3

Посмотрите, как этоработает?Часть динамического программирования работает в обратном направлении: как только вы вычислили f (9) в первый раз (при вычислении f (8)), вы запомните результат и не будете повторять вычисления при вычислении f (0).