Python 中的跳跃游戏问题

在这个问题中，我们将有一个整数数组。数组中每个索引处的整数指定了我们可以从该索引跳出的最大长度。我们需要找出到达数组最后一个索引所需的跳跃次数。我们需要返回所有跳跃次数中的最小值。如果无法通过任何路径到达终点，则为该数组返回 -1。

让我们看一些例子来理解这个问题。

输入: 数组 = [1, 2, 6, 8, 6, 3, 6, 0, 1, 2, 9]

输出 3 (1--> 2 --> 8 --> 9)

解释: 我们将从第 0 个索引开始。第 0 个索引处的整数是 1，因此我们最多可以跳到第 1 个索引。接下来，从第 1 个索引，我们可以向前跳 2 个索引。因此，我们将到达索引 3。从索引 3，我们可以向前跳 8 步。因为 8 + 3 = 11，这等于数组的长度。因此，从索引 3，我们将跳到数组的最后一个索引之外。我们跳了 3 次到达终点。所以答案是 3。

输入: 数组 = [1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1]

输出 5

解释: 我们将应用与上面示例相同的逻辑。我们将从第 0 个索引跳到第 1 个索引，然后跳到第 2 个索引。从第 2 个索引向前，我们将跳 2 个索引，到达第 4 个、然后是第 6 个、然后是第 8 个，最后是第 10 个索引。到达最后一个索引所需的总跳跃次数为 10。

方法 - 1

在第一种方法中，我们将使用递归来解决问题。

我们首先创建一个递归函数。我们将递归地为从当前元素可以到达的所有索引调用该函数。我们可以计算出数组中的所有可能路径，并找到最短路径或跳跃次数最少的路径。

我们将按照以下步骤解决此问题。

• 我们将首先定义一个递归函数。
• 然后我们将指定此递归函数的基线条件。
• 在下一步中，我们将递归地调用此函数。通过每次递归调用，我们将获得所有可从当前索引到达的索引，基于跳跃限制。因此，我们将为每个索引调用此函数。
• 然后最后一步是找到从当前索引到数组最后一个索引所需的最小跳跃次数。
• 我们将返回所需的最小跳跃次数。

下面是上面算法的 Python 程序。

代码

输出

The minimum jumps required to reach the end of the array is: 3

时间复杂度: 从任何给定索引向前移动最多有 n 种可能的方式。因此，到达终点所需的最大步数为 nⁿ。所以时间复杂度是 O(n * Nⁿ)。

空间复杂度: 我们需要 O(n) 的内存来存储递归栈。

方法 - 2

在第二种方法中，我们将使用动态规划。一些重叠的条件会花费额外的时间；因此，使用动态规划将是有效的。

让我们通过一个例子来理解。让我们取数组 = [1, 2, 1, 8, 6, 3, 6, 0, 1, 2, 9]。递归函数 minNoJumps(3, 10) 将被调用两次，因为一个人可以从索引 1 和 2 到达 8。因此，这是一个重叠的子问题。我们可以使用动态规划解决方案来避免这种重叠的子问题。

我们将按照以下步骤解决问题

• 我们将创建一个数组 dp = []。我们将填充数组 dp，使得 dp[i] 将存储从索引 0 开始到达索引 I 所需的最小跳跃次数。最初，我们将 dp[i] 设置为 float("inf")。
• 我们将使用嵌套的 Python 循环填充此数组。
• 外层 for 循环的范围是 1 到 n - 1，而内层循环的范围是 0 到 i。
• 如果 i 的值小于 j + array[j]，那么我们将 dp[i] 设置为 dp[i] 和 dp[i] + 1 之间的最小值。
• 最后，我们将返回数组 dp 中最后一个索引处的值。

下面是上述方法的 Python 代码。

代码

输出

The minimum jumps required to reach the end of the array is: 3 

时间复杂度: 此方法的实际时间复杂度比前一种方法大大降低。复杂度降低是因为我们不需要多次运行各种子问题。由于有两个嵌套循环，因此时间复杂度是非线性的；因此，它是 O(n2)。

空间复杂度: 我们正在存储长度为 n 的 dp 数组，这将在内存中占用线性空间。因此，此方法的空间复杂度为 O(n)。

方法 - 3

这种方法是我们上面看到的动态规划方法的变体。

我们将再次创建一个数组 dp = []。然而，这次 dp 的第 i 个索引将告诉从数组的第 i 个索引到达 (n - 1) 个索引所需的最小跳跃次数。因此，在程序结束时，我们将返回第一个索引的值，即数组 dp 的第 0 个索引。这种方法将告诉从第 0 个索引到达 (n - 1) 个索引所需的最小跳跃次数。

以下是此方法的 Python 代码。

代码

输出

The minimum jumps required to reach the end of the array is: 3

时间复杂度: 由于我们运行了嵌套循环，因此时间复杂度将是非线性的。因此，它是 O(n2)。

空间复杂度: 我们使用了额外的空间来存储 DP 数组。因此

空间复杂度为 O(n)。

方法 - 3

我们将使用贪婪算法来解决这个问题。

下面是要遵循的步骤。

• 首先，我们将检查数组是否为空或只包含一个元素。如果此条件为真，我们已经到达数组的末尾，因此我们将返回 0 次跳跃。
• 遵循此条件，我们将检查数组的第一个元素是否为 0。如果第一个元素是 0，我们就无法前进，因此无法到达数组的末尾。因此，我们将返回 -1。
• 我们将初始化三个变量。第一个将包含最大可达范围 max_reach = 0，第二个变量将跟踪当前可达范围 curr_reach = 0，第三个变量将计算跳跃次数 no_jumps = 0。
  • 现在我们将从第一个到最后一个遍历数组。
  • 首先，我们将检查当前索引是否超过了可能的最大可达范围。如果此条件为真，我们就无法到达数组的末尾，因此我们将返回 -1。
  • 我们将检查的下一个条件是数组索引 I 处的值是否大于到目前为止的最大可达范围。如果是，我们可以超出当前 max_reach 值。因此，我们将 max_reach 更新为 i + array[i]。
  • 要检查的最后一个条件是当前索引是否等于 curr_reach。如果此条件为真，则表示要进一步前进，我们需要跳跃。因此，如果此条件为真，我们将增加跳跃计数器 no_jumps。此外，我们将 curr_reach 更新为等于 max_reach，这将检查我们下次何时需要跳跃。
• 最后，我们将返回 no_jumps 变量中存储的跳跃次数。

下面是实现贪婪算法方法的 Python 程序。

代码

输出

The minimum jumps required to reach the end of the array is: 3

时间复杂度: 我们执行了一个线性循环；因此时间复杂度将是线性的。O(n)。

空间复杂度: 我们没有使用任何额外的空间；因此，空间复杂度是常数，即 O(1)。

贪婪算法是所有方法中最好的，具有线性的时间和常数的空间复杂度。