Pythonで隣接する木の高さがすべて異なるようにするための最小コストを求めるプログラム

問題の概要

植物の高さを表す整数リスト heights と、各植物の高さを1つ増やすのに必要なコストを表すリスト costs が与えられます。隣り合う植物どうしの高さがすべて異なるようにするために必要な最小コストを求めるのが目的です。

たとえば、heights = [3, 2, 2]、costs = [2, 5, 3] という入力の場合、出力は 3 になります。最後の植物の高さを1だけ増やせば(コスト3)、リストは [3, 2, 3] となり、隣接する高さがすべて異なる状態になるからです。

解き方のアプローチ(動的計画法)

この問題は動的計画法(DP)を使うと効率的に解けます。ポイントは、各植物の高さを「そのまま」「+1」「+2」の3択で考えることです。仮に左隣と高さが被っても、最大2つ増やせば必ず重ならない高さにできるため、探索範囲は0〜2で十分です。

具体的な手順は次のとおりです。

• dp(idx, l_height) 関数を定義する:idx は現在見ている植物の位置、l_height は左隣の植物の最終的な高さを表します。
• ベースケース:idx が最後の要素(len(heights) - 1)のとき、heights[idx] が l_height と異なれば 0 を返し、同じであれば costs[idx](1増やすしかないため)を返します。
• 遷移:ret を無限大で初期化し、i を 0〜2 の範囲で動かします。heights[idx] + i が l_height と異なるときだけ、「dp(idx + 1, heights[idx] + i) + costs[idx] * i」の最小値で ret を更新します。
• 結果の返却:ret を返し、全体の答えは dp(0, None) となります。

Pythonでの実装例

以下は実際の実装です。素朴な再帰だけでは同じ状態を何度も計算してしまうため、@lru_cache によるメモ化を追加しています。これにより計算量が指数オーダーから線形オーダー(O(n))へ改善されます。

from functools import lru_cache

class Solution:
    def solve(self, heights, costs):
        n = len(heights)

        @lru_cache(maxsize=None)
        def dp(idx, l_height):
            # 最後の要素:左隣と重なっていれば1増やすコストが必要
            if idx == n - 1:
                return 0 if heights[idx] != l_height else costs[idx]
            ret = float("inf")
            for i in range(3):  # 高さを 0〜2 増やす選択肢を試す
                if heights[idx] + i != l_height:
                    ret = min(ret, dp(idx + 1, heights[idx] + i) + costs[idx] * i)
            return ret

        return dp(0, None)

ob = Solution()
heights = [3, 2, 2]
costs = [2, 5, 3]
print(ob.solve(heights, costs))

入力

[3, 2, 2], [2, 5, 3]

出力

3

計算量の目安

メモ化を行うことで、状態は「位置 idx × 増分の選択肢(3通り)」に限定されるため、時間計算量・空間計算量ともに O(n) で済みます。一方、メモ化なしの素朴な再帰では最大 3^n 通りの呼び出しが発生するため、入力サイズが大きくなると実用的ではなくなります。