【Python】リストの先頭（インデックス0）から最後の位置に到達できるか判定するプログラム

数値のリスト nums があるとします。各要素は、その位置から一度に進める最大ジャンプ数を表しています。このとき、インデックス0からスタートして、リストの最後のインデックスに到達できるかどうかを判定する必要があります。

例えば、入力が nums = [2,5,0,2,0] の場合、出力は True になります。これは、インデックス0から1へジャンプし、さらにインデックス1（値が5なので最大5つ先まで進める）から最後のインデックスへ直接ジャンプできるためです。

解法のアプローチ

この問題は動的計画法（DP）を使って効率的に解くことができます。ポイントは、リストを後ろから前に向かって走査し、「その位置から最後のインデックスに到達できるか」を順番に求めていくことです。

具体的な手順は以下の通りです。

• n := nums の要素数とします

• arr := サイズ n の配列を作成し、すべて False で初期化します

• arr[n - 1] := True と設定します（最後のインデックス自体には常に到達可能なため）

• i を n - 2 から 0 まで 1 ずつ減らしながら以下を繰り返します

  • arr[i] := インデックス i + 1 から i + nums[i] までの範囲にある arr の要素が一つでも True であれば True とします

• 最後に arr[0] を返します

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

実装例

class Solution:
   def solve(self, nums):
      n = len(nums)
      arr = [False] * n
      arr[n - 1] = True
      for i in range(n - 2, -1, -1):
         arr[i] = any(arr[i + 1 : i + nums[i] + 1])
      return arr[0]
ob = Solution()
nums = [2,5,0,2,0]
print(ob.solve(nums))

入力

[2,5,0,2,0]

出力

True

計算量について

このアルゴリズムの時間計算量は O(n²) です。各位置 i について、最大 nums[i] 個の到達可能な位置を確認する必要があるためです。一方、空間計算量は O(n) となり、DPテーブルの分だけ追加のメモリを使用します。