algorithm - 我如何找到通过 bool 数组的路径？

Question

这是我在面试论坛上遇到的一个问题:

You have an array filled with 0s and 1s. A 0 represents burning lava, and a 1 represents a stepping stone. You start at the beginning of the array, and you want to find the fastest way to reach the end. At each time step, you can either increase or decrease your velocity V by 1, or you can jump to a stepping stone V steps away. You want to reach the end of the array without overshooting.

解决这个问题的好算法是什么？

我尝试了一些方法(主要是使用动态规划和递归)，但我无法找出会导致非指数算法的最佳子结构。有什么想法吗？

Answer 1

在每个步骤中，您有两个选择:增加速度或不增加速度。然后，对于这些选项中的每一个，您最终都会进入不同的步骤并重复选择。也许你可以看到这里出现的树状图案。树中的每个节点都是一个步骤，每条边都是一个选择。每个节点(step)都有两条边(choices)，所以是一棵二叉树。

另请注意，如果您以 V 的速度处于 x 步，那么您如何到达那里并不重要，接下来的结果将是相同。所以这里可以稍微优化一下。 (例如，使用动态规划。)

蛮力方法就是想象这棵树并进行深度优先搜索，直到您准确地到达结束步骤。可能有多种解决方案，最快的是解决方案。