Pythonで配列の最小調整コストを求める方法【動的計画法で解説】

問題の概要

正の整数からなる配列が与えられたとします。ここで、配列内の隣接する2つの要素の差が、指定された値 target 以下になるように、各要素を新しい値へ置き換えることを考えます。

このとき、元の値と新しい値の差の絶対値の合計、すなわち調整コストを最小化することが目的です。数式で表すと、次の合計を最小化することになります。

Σ |A[i] − A_new[i]|　（i は 0 から n−1 まで）

ここで、n は配列 A のサイズ、A_new は隣接要素間の差が target 以下となるように調整した後の配列です。

入出力の例

たとえば、入力が次の場合を考えてみましょう。

[56, 78, 53, 62, 40, 7, 26, 61, 50, 48], target = 20

この場合、出力は 35 となります。

解法のアプローチ（動的計画法）

この問題は動的計画法（DP）を使うことで効率的に解けます。手順は以下のとおりです。

• n := 配列 arr のサイズとします。

• M := 要素が取りうる最大値（ここでは 100）とし、(n × (M+1)) の2次元テーブル table を用意します。table[i][j] は「i 番目の要素を値 j に調整したときの、先頭からの累積最小コスト」を表します。

• 初期条件として、table[0][j] := |j − arr[0]| を設定します。

• i を 1 から n−1 まで動かしながら、各 i・j について次のように遷移を計算します。

  • table[i][j] := 100000000（十分大きな値で初期化）

  • k を max(j − target, 0) から min(M, j + target) まで動かし、table[i][j] := min(table[i][j], table[i−1][k] + |arr[i] − j|) を更新します。

• 最後に ans := 10000000 で初期化し、j を 0 から M まで動かしながら ans := min(ans, table[n−1][j]) を計算します。

• ans を返します。これが求める最小調整コストです。

Pythonでの実装例

それでは、実際のPythonコードを見てみましょう。

M = 100

def get_min_cost(arr, target):
    n = len(arr)
    table = [[0 for i in range(M + 1)] for i in range(n)]
    # 初期化：0番目の要素を j に変更するコスト
    for j in range(M + 1):
        table[0][j] = abs(j - arr[0])
    # 動的計画法による遷移
    for i in range(1, n):
        for j in range(M + 1):
            table[i][j] = 100000000
            for k in range(max(j - target, 0), min(M, j + target) + 1):
                table[i][j] = min(table[i][j], table[i - 1][k] + abs(arr[i] - j))
    # 最終行の最小値が答え
    ans = 10000000
    for j in range(M + 1):
        ans = min(ans, table[n - 1][j])
    return ans

arr = [56, 78, 53, 62, 40, 7, 26, 61, 50, 48]
target = 20
print(get_min_cost(arr, target))

入力

[56, 78, 53, 62, 40, 7, 26, 61, 50, 48], 20

出力

35

処理のポイント

• 状態の定義： table[i][j] は「i 番目の要素を値 j に調整した場合の、先頭から i 番目までの最小累積コスト」を表します。

• 制約の反映： 内側のループで k の範囲を max(j − target, 0) ～ min(M, j + target) に限定することで、「隣接要素の差が target 以下」という条件を自然に組み込んでいます。

• 計算量： 計算量は O(n × M × target) 程度です。要素数や値の範囲が限られているケースでは、十分実用的な速度で動作します。

まとめ

隣接要素間の差を target 以下に抑えながら調整コストを最小化する問題は、動的計画法を用いることで体系的に解くことができます。各要素が取りうる値ごとに累積コストを記録し、制約範囲内の遷移だけを考慮することで、最適な調整方法を見つけられます。本記事のコードを参考に、ぜひ自分のデータでも試してみてください。