Pythonで解く「ジャンプゲーム II」：最小ジャンプ回数を求める貪欲法アルゴリズム

問題概要

すべての要素が正の整数である配列が与えられます。初期位置はインデックス0で、配列の各要素はその位置からジャンプできる最大距離を表します。目標は、最後のインデックスに到達するために必要なジャンプ回数を最小化することです。

例えば、配列が [2,3,1,1,4] の場合、答えは 2 になります。インデックス0からインデックス1へジャンプし、そこからインデックス4（最後のインデックス）へ一気にジャンプできるためです。

解法のアプローチ（貪欲法）

この問題は、貪欲法（Greedy法）を使うことで線形時間で効率的に解けます。ポイントは、「現在のジャンプ1回で届く範囲の境界」と「次に到達可能な最も遠い位置」を同時に追跡していくことです。

手順は以下の通りです。

• end := 0、jumps := 0、farthest := 0 で初期化する

• i を 0 から len(nums) − 1 までループする

  • farthest := max(farthest, nums[i] + i)

  • i == end かつ i != len(nums) − 1 の場合：

    • jumps を 1 増やす

    • end := farthest と更新する

• 最後に jumps を返す

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([2,3,1,1,4]))

入力

[2,3,1,1,4]

出力

2

アルゴリズムのポイント

この手法は幅優先探索（BFS）に近い発想に基づいています。変数 end は「現在のジャンプ1回で到達できる範囲の境界」を表し、farthest は次のジャンプで届きうる最遠位置を記録します。インデックス i が end に達した時点で、それ以上進むには新たなジャンプが必須になるため、jumps を1増やし、end を farthest に更新します。

計算量は時間・空間ともに O(n) となり、各位置からの遷移を全て試す動的計画法（O(n²)）よりも大幅に高速です。LeetCode の「Jump Game II」などでも定番の解法として知られています。