用 Python 编写程序，查找到达终点所需的最小跳数

pythonserver side programmingprogramming更新于 2026/2/2 2:52:17

假设我们有一个数组 nums，其中所有元素都是正数。我们位于索引 0。这里，数组中的每个元素代表我们在该位置的最大跳跃长度。我们的目标是以较少的跳跃次数到达最终索引(n-1，其中 n 是 nums 的大小)。因此，如果数组为 [2,3,1,1,4]，则输出将为 2，因为我们可以从 0 跳转到索引 1，然后跳转到索引 4，即最后一个索引。

为了解决这个问题，我们将遵循以下步骤 −

end := 0, jumps := 0, farthest := 0
for i in range 0 to length of nums – 1
- farthest := farthest 和 nums[i] + i 的最大值
- 如果 i 是 end，并且 i 不是 nums – 1 的长度，则
  - 将 jumps 增加 1
  - end := farthest
返回 jumps

让我们看看下面的实现以便更好地理解 −

示例

class Solution(object):
   def jump(self, nums):
      end = 0
      jumps = 0
      farthest = 0
      for i in range(len(nums)):
         farthest = max(farthest,nums[i]+i)
         if i == end and i != len(nums)-1:
            jumps+=1
            end = farthest
      return jumps
ob = Solution()
print(ob.jump([3, 4, 3, 0, 1]))