Pythonで最後のインデックスに到達するための最小ジャンプ回数を求めるプログラム

問題の概要

すべての要素が正の整数である配列 nums があるとします。現在、私たちはインデックス 0 の位置にいます。配列の各要素は、その位置からジャンプできる最大距離を表しています。目標は、できるだけ少ないジャンプ回数で最後のインデックス(n-1)に到達することです。

例えば、配列が [2,3,1,1,4] の場合、出力は 2 になります。これは、インデックス 0 からインデックス 1 へジャンプし、そこからインデックス 4(最後のインデックス)へジャンプすればよいためです。

解決のための手順

• end := 0、jumps := 0、farthest := 0 で初期化する
• i を 0 から nums の長さ - 1 まで繰り返す
  • farthest := max(farthest, nums[i] + i) とする
  • i が end と等しく、かつ i が nums の長さ - 1 でない場合:
    • jumps を 1 増やす
    • end := farthest とする
• jumps を返す

アルゴリズムのポイント(貪欲法)

このアルゴリズムは貪欲法(Greedy法)を利用しています。現在のジャンプ範囲の終端(end)に達した時点で、それまでに到達可能だった最も遠い位置(farthest)を次のジャンプ範囲の終端として設定し、ジャンプ回数を 1 増やします。こうすることで、各ジャンプでできるだけ遠くまで進むことが保証され、結果として最小のジャンプ回数が求まります。時間計算量は O(n)、空間計算量は O(1) と非常に効率的です。

理解を深めるために、以下の実装例を見てみましょう。

実装例(Python)

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]))

入力

[3, 4, 3, 0, 1]

出力

2

この例では、インデックス 0 から 1 回目のジャンプで最大 3 先まで進めます。ここで範囲の終端に達すると、farthest に記録された最遠位置が新しい終端となり、2 回目のジャンプで最後のインデックスに到達できます。そのため、答えは 2 となります。