计算跨越障碍到达目的地的可能方式数量？

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）时不要重复计算。