Pythonでリストを非増加リストに変換するために必要な最小操作回数を求めるプログラム

問題概要

数値のリスト nums が与えられたとします。使用できる操作は「隣接する2つの値を選び、その合計値を持つ1つの値にマージする」ことだけです。この操作を繰り返してリスト全体を非増加(左から右へ値が増加しない状態)にするとき、必要となる最小の操作回数を求めます。

たとえば、入力が nums = [2, 6, 4, 10, 2] の場合を考えてみましょう。まず先頭の [2, 6] をマージして [8, 4, 10, 2] とし、続けて [8, 4] をマージして [12, 10, 2] とすれば、リストは非増加になります。操作は2回なので、答えは 2 です。

解法の考え方(動的計画法)

この問題は、リストを右から左へ処理する動的計画法(DP)で効率的に解くことができます。鍵となるのは次の2つの配列です。

• arr[i]: 位置 i から始まる「ブロック」を適切にマージした結果の値(ブロックの代表値)
• dp[i]: 位置 i 以降を非増加にするために必要な最小マージ回数

各位置 i では、現在のブロックの値 x が右隣のブロックの値 arr[j+1] より小さい間、隣接要素をマージし続けます。こうすることで、すべてのブロックが「自分より右のブロック以上」という条件を満たし、リスト全体が非増加になります。

アルゴリズムの手順

• nums が空なら 0 を返す
• nums の末尾に -inf(負の無限大)を挿入する(番兵として境界判定を簡単にする)
• N := nums のサイズ
• dp := サイズ N のリスト(すべて 0 で初期化)
• arr := サイズ N のリスト(すべて 0 で初期化)
• p := arr のサイズ
• arr[p−1] := nums[N−1]、arr[p−2] := nums[N−2](末尾2つのブロックを確定)
• i を N−3 から 0 まで 1 ずつ減らしながら以下を実行:
  • j := i、x := nums[j]
  • j < N−1 かつ x < arr[j+1] の間、j := j+1、x := x + nums[j] を繰り返す
  • dp[i] := j − i + dp[j+1]
  • arr[i] := x
• dp[0] を返す

なお、単調増加列のような最悪ケースでは計算量は O(N²) になりますが、多くのケースでは非常に高速に動作します。

実装例(Python)

class Solution:
    def solve(self, nums):
        if not nums:
            return 0
        nums.append(float("-inf"))
        N = len(nums)
        dp = [0] * N
        arr = [0] * N
        arr[-1] = nums[-1]
        arr[-2] = nums[-2]
        for i in range(N - 3, -1, -1):
            j = i
            x = nums[j]
            while j < N - 1 and x < arr[j + 1]:
                j += 1
                x += nums[j]
            dp[i] = j - i + dp[j + 1]
            arr[i] = x
        return dp[0]

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

入力

[2, 6, 4, 10, 2]

出力

2

動作の追跡(例: [2, 6, 4, 10, 2])

右から順に処理したとき、各位置でのブロック値とマージ回数は次のようになります。

最終的に dp[0] = 2 が答えとなり、実際のリストも [12, 10, 2] という非増加列になっていることが確認できます。

コードのポイント

• 番兵(-inf): 末尾に -inf を追加しておくことで、while ループの境界判定がシンプルになり、最後の要素に対する特別な処理が不要になります。
• 右からのDP: 右側の結果(dp[j+1])が先に確定しているため、左へ向かって順に計算を進められます。
• 貪欲なマージ: 各位置で「右隣のブロック以上になるまでマージする」という貪欲戦略が最適解につながります。