使用分而治之找到青蛙穿越池塘跳跃次数最少的路径

Question

一只青蛙正试图穿过池塘，但他只能在石头上跳跃，最多能跳五个单位。

我们得到了一个包含1和0（水为0，石头为1）的数组，任务是找到可能的最佳方法，以找到跳跃次数最少的路径（如果可能，使用分治）。

数组示例-

我刚刚开始学习算法，所以如果你们能帮我学习算法和代码就好了。

Answer 1

我对分而治之方法的想法如下：

program frog(array)
begin
  divide array after the '1' left of the center of the array;
  foreach (partialArray) do begin
    if (length(partialArray) > 5) then frog(partialArray);
  end foreach;
end.

让我们以给定的数组为例：[0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0]

• 1^st部门：[0 0 0 1 0 0 1 0 0 1 | 0 1 0 0 1 0 1 0 0 0 0 0]
• 2^nd部门：[0 0 0 1 | 0 0 1 | 0 1 0 0 1 | 0 1 0 0 0 0 0]
• 3^rd部门：[0 0 0 1 | 0 0 1 | 0 0 1 | 0 0 1 | 0 0 0 0 0 0]

在这种情况下，青蛙会跳到第一个、第二个、第三个、第五个和第七个1，然后才能达到目标（=6跳）。

为什么这个算法有效？让我们假设，它不会输出青蛙跳跃的最短路径。这意味着，我们没有找到青蛙跳跃最大的partialArrays。如果一个partialArray不会像一个最大的跳跃，那就意味着：在1之后，partialArray内部至少有一个1，青蛙仍然可以到达。这是不可能的，因为length（partialArray）≤ 5有效。因此，partialArray之后的每个1都会太远（