这是我在面试论坛上遇到的一个问题：
你有一个用 0 和 1 填充的数组。0 代表燃烧的熔岩，1 代表踏脚石。您从数组的开头开始，并且想要找到到达结尾的最快方法。在每个时间步，您可以将速度 V 增加或减少 1，或者您可以跳到 V 步外的垫脚石。您希望在没有超调的情况下到达数组的末尾。
什么是解决这个问题的好算法？
我尝试了一些东西（主要使用动态编程和递归），但我无法找出会导致非指数算法的最佳子结构。有任何想法吗？
问问题
101 次
2 回答
1
在每一步你有两个选择：增加速度，或者不增加速度。然后，对于这些选项中的每一个，您最终都会进入不同的步骤并重复选择。也许你可以看到这里出现的树状图案。树中的每个节点都是一个步骤，每个边都是一个选择。每个节点（步骤）都有两条边（选择），所以它是一棵二叉树。
另请注意，如果您以速度V处于第x步，那么无论您如何到达那里，接下来的结果都是相同的。所以在这里你可以优化一下。（例如，使用动态规划。）
蛮力方法就是想象这棵树并进行深度优先搜索，直到您准确地到达最后一步。可能有多种解决方案，最快的一个是解决方案。
于 2013-03-22T01:33:36.820 回答
1
动态编程是这里的正确方法。
您的搜索空间是二维的：当前位置是您的第一维，当前速度是第二维。这意味着您需要一个二维数组best[N][N]，其中N是布尔数组中的项目数。的值表示以 的速度best[s,v]到达 的位置所需的最小步数。检查搜索空间的每个点以检查是否可以以当前速度到达垫脚石。如果答案是“是”，则在搜索空间中设置相应的位置。还要设置相邻速度的点。答案将在位置。svbest[N-1][0]
于 2013-03-22T01:50:44.913 回答