【Python】ジャンプゲームで取得できる最大スコアを求めるプログラムの書き方

問題の概要

nums という整数型の配列と、値 k が与えられているとします。プレイヤーはインデックス 0 からスタートし、1 回の移動につき、配列の境界外に出ない範囲で最大 k ステップだけ右へジャンプできます。目標は、配列の最後のインデックスに到達することです。

ジャンプによって得られるスコアは、「訪れたすべてのインデックス j における nums[j] の合計」です。このとき、取得できるスコアの最大値を求める必要があります。

たとえば、入力が nums = [1, -2, -5, 7, -6, 4]、k = 2 の場合、出力は 10 になります。[1, -2, 7, 4] の順にジャンプすると、最大スコアとなる 10 が得られるためです。

解法の考え方

この問題は動的計画法（DP）を使って効率よく解けます。「各インデックスに到達したときの最大スコア」を順に計算していき、あわせて直近 k 個のウィンドウ内での最大値を追跡するのがポイントです。手順は以下の通りです。

• n := nums のサイズ
• scores := サイズ n・すべて 0 で初期化された配列
• scores[0] := nums[0]
• currMax := scores[0]
• max_pt := 0
• n < 1 の場合は 0 を返す
• n が 1 の場合は nums の末尾の要素を返す
• idx を 1 から n - 1 まで繰り返す
  • max_pt >= idx - k の場合：
    currMax < scores[idx-1] かつ idx > 0 であれば、currMax := scores[idx-1]、max_pt := idx - 1 に更新する
  • それ以外の場合（idx - k > 0 のとき）：
    currMax := scores[idx-k]、max_pt := idx - k とし、p を idx-k から idx まで走査しながら、scores[p] >= currMax なら max_pt := p、currMax := scores[p] として、ウィンドウ内の最大値を再計算する
  
  最後に scores[idx] := currMax + nums[idx] とする
• ループ終了後、scores の末尾 := currMax + nums[-1]
• scores の末尾の要素を返す

この実装では、「ジャンプ可能な範囲（直近 k インデックス）の中で最もスコアの高い位置」を常に追跡することで、毎回全要素を確認し直す必要がなくなり、全体の計算量を抑えられるようになっています。

実装例

以下の実装を見ると、理解がより深まるでしょう。

def solve(nums, k):
   n = len(nums)
   scores = [0] * n
   scores[0] = nums[0]
   currMax = scores[0]
   max_pt = 0

   if n < 1:
      return 0
   if n == 1:
      return nums[-1]

   for idx in range(1,n):
      if max_pt >= idx - k:
         if currMax < scores[idx-1] and idx > 0:
            currMax = scores[idx-1]
            max_pt = idx-1
      else:
         if idx - k > 0:
            currMax = scores[idx-k]
            max_pt = idx - k
            for p in range(idx-k, idx):
               if scores[p] >= currMax:
                  max_pt = p
                  currMax = scores[p]
      scores[idx] = currMax + nums[idx]
   scores[-1] = currMax + nums[-1]
   return scores[-1]

nums = [1,-2,-5,7,-6,4]
k = 2
print(solve(nums, k))

入力

[1,-2,-5,7,-6,4], 2

出力

10