Pythonで数値を削除して最大の加算スコアを求めるプログラム|区間DPによる解法

問題の概要

数値のリスト nums が与えられます。次のような操作を考えます。

• リストの先頭と末尾以外から数値を1つ選び、取り除きます。
• その際、「選んだ数値 + 両隣の数値」の合計がスコアに加算されます。
• この操作は、先頭と末尾を選ばない限り何度でも繰り返せます。

このとき、最終的に得られるスコアの最大値を求めるのが目的です。

入力例と動作の確認

入力が nums = [2, 3, 4, 5, 6] の場合、出力は 39 になります。手順は以下の通りです。

1. 5 を選択:スコアは (4 + 5 + 6) = 15、配列は [2, 3, 4, 6] になります。
2. 4 を選択:スコアは (3 + 4 + 6) = 13、配列は [2, 3, 6] になります。
3. 3 を選択:スコアは (2 + 3 + 6) = 11、配列は [2, 6] になります。

合計スコアは 15 + 13 + 11 = 39 です。

解法のアプローチ:区間DP

この問題は区間DP(インターバルDP)で効率的に解けます。dp[i][r] を「元の配列において位置 i と位置 r に挟まれた区間内の要素をすべて取り除いたときの最大スコア」と定義します。

ポイントは、区間 (i, r) 内で最後に取り除く要素を k とすると、その時点で k の両隣は必ず位置 i と位置 r の要素になっているという点です。したがって、最後の1回で得られるスコアは「nums[i] + nums[k] + nums[r]」で確定します。これにより次の漸化式が導かれます。

dp[i][r] = max(dp[i][k] + dp[k][r] + nums[k]) + nums[i] + nums[r](i < k < r)

アルゴリズムの手順

1. n を nums のサイズとします。
2. n < 3 の場合は、除去できる要素が存在しないため 0 を返します。
3. (n + 1) × (n + 1) の2次元配列 dp を用意します(初期値はすべて 0)。
4. 区間長 len を 3 から n まで1ずつ増やしながら、以下を繰り返します。
   • 左端 i を「i + len − 1 ≤ n」を満たす範囲で動かし、右端を r = i + len − 1 とします。
   • k を i + 1 から r − 1 まで動かし、curr = dp[i][k] + dp[k][r] + nums[k−1] の最大値を ans とします。
   • ans に nums[i−1] + nums[r−1] を加えた値を dp[i][r] に格納します。
5. 最後に dp[1][n] を返します。

※ 実装では dp を1始まりのインデックスで管理するため、nums へのアクセスは k−1、i−1、r−1 となります。

Pythonでの実装例

class Solution:
   def solve(self, nums):
      n = len(nums)
      if n < 3:
         return 0
      dp = [[0] * (n + 1) for _ in range(n + 1)]
      for length in range(3, n + 1):
         for i in range(1, n - length + 2):
            r = i + length - 1
            ans = 0
            for k in range(i + 1, r):
               curr = dp[i][k] + dp[k][r] + nums[k - 1]
               if curr > ans:
                  ans = curr
            ans += nums[i - 1] + nums[r - 1]
            dp[i][r] = ans
      return dp[1][n]

ob = Solution()
nums = [2, 3, 4, 5, 6]
print(ob.solve(nums))

入力

[2, 3, 4, 5, 6]

出力

39

計算量

• 時間計算量:O(n³)(区間長・左端・分割位置 k の三重ループ)
• 空間計算量:O(n²)(DPテーブルの保持)

まとめ

「要素を取り除くと両隣との和が得られる」タイプの問題は、最後に取り除く要素に着目して区間を分割することで、区間DPとして定式化できます。区間長を小さい順に埋めていけば、部分問題の結果を再利用しながら全体の最大スコアを求められます。全探索では指数時間かかる場面でも、この手法なら大規模な入力にも対応可能です。