Pythonで解くジャンプゲーム問題 ― 最後のインデックスに到達できるか判定するアルゴリズム

ジャンプゲーム問題とは

非負の整数からなる配列が与えられ、最初は配列の先頭(インデックス0)にいるものとします。各要素は、その位置から最大で何ステップ先へジャンプできるかを表しています。このとき、配列の最後のインデックスに到達できるかどうかを判定するのがこの問題です。

例として、配列 [2,3,1,1,4] を考えてみましょう。インデックス0から1へ1ステップ移動し、次にインデックス1から最大3ステップ跳べるため、そのまま最後まで到達できます。したがって答えは True になります。

解法のアプローチ:後ろから追跡する貪欲法

この問題は、配列を後ろから走査する貪欲法(Greedy)で効率よく解けます。考え方はシンプルで、「現在到達可能な最左の位置」を管理しながら左へ更新していくというものです。

手順

• 変数 n を「ゴールとなるインデックス」として、配列の長さ − 1 で初期化します。
• i を n − 1 から 0 まで逆順にループさせます。
• 各 i について、nums[i] + i >= n(つまり位置 i からゴール n に届く)であれば、n を i に更新します。これで i も新たな「到達可能な位置」になります。
• ループ終了後、n == 0 ならば先頭からゴールへ到達できるので True を返し、そうでなければ False を返します。

この方法なら、実際にジャンプ経路を構築する必要がなく、一度の走査で判定が完了します。

Pythonでの実装例

class Solution(object):
    def canJump(self, nums):
        n = len(nums) - 1
        for i in range(n - 1, -1, -1):
            if nums[i] + i >= n:
                n = i
        return n == 0

ob1 = Solution()
print(ob1.canJump([2, 3, 1, 1, 4]))

入力

[2,3,1,1,4]

出力

True

計算量について

• 時間計算量: O(n) ― 配列を一度だけ走査するため、要素数に対して線形時間で処理できます。
• 空間計算量: O(1) ― 追加の配列やメモを必要とせず、変数 n のみで完結します。

まとめ

ジャンプゲーム問題は、ゴール側から「到達可能な位置」を左へと縮めていく貪欲法が有効です。条件を満たすたびにゴール位置を手前に移動させ、最終的にそれがインデックス0まで届けば到達可能と判定できます。シンプルな実装でありながら計算量も抑えられるため、面接対策や競技プログラミングでも頻出のテクニックです。