Pythonで本棚の高さを最小化する：動的計画法による解法

問題の概要

一連の本があるとしましょう。ここで、i番目の本は厚さ books[i][0]、高さ books[i][1] で表されます。これらの本を、幅が shelf_width の本棚に、与えられた順序どおりに並べていきたいと思います。

同じ棚には、厚さの合計が shelf_width 以下になる範囲で複数の本を置けます。それ以上置けなくなったら、新しい段を作成します。このとき、本棚全体の高さは、その段に置いた本の中で最も高い本の高さぶんだけ増加します。すべての本を置き終えるまで、この手順を繰り返します。

ただし重要なルールとして、各ステップで本を置く順序は、必ず与えられた本の並び順と同じでなければなりません。この条件のもとで、本棚全体の高さとして考えられる最小値を求めるのが目的です。

入力例

例えば、入力が [[1,1], [2,3], [2,3], [1,1], [1,1], [1,1], [1,2]]、shelf_width = 4 の場合を見てみましょう。

この場合の出力は 6 になります。3つの棚の高さの合計が 1 + 3 + 2 = 6 となるためです。なお、2冊目の本が最初の棚に置かれている必要はない点に注意してください。

解き方のアプローチ

この問題は動的計画法（DP）を使うことで効率的に解けます。「dp[i] = i番目までの本を配置したときの最小の高さ」と定義し、以下の手順で計算を進めていきます。

• 本の数と同じサイズの配列 dp を作成し、無限大で初期化する
• dp[0] := books[0][1] と設定する
• i を 1 から（本の総数 − 1）まで繰り返す：
  • curr_height := 0、temp := shelf_width、j := i で初期化する
  • j >= 0 かつ temp − books[j][0] >= 0 の間、以下を繰り返す：
    • curr_height := max(books[j][1], curr_height)
    • dp[i] := min(dp[i], curr_height + （j − 1 >= 0 なら dp[j−1]、そうでなければ 0）)
    • temp := temp − books[j][0]
    • j を 1 減らす
• dp の最後の要素を返す

このアルゴリズムでは、各位置 i について「現在の本から遡って、同じ棚に載せられる範囲の本をまとめて一段に置いた場合」の高さをすべて試行します。これにより、棚の区切り位置を全パターン検討しながら、最適な配置を見つけることができます。時間計算量は O(n²)、空間計算量は O(n) となります。

実装例

理解を深めるために、以下の実装を見てみましょう。

class Solution(object):
    def minHeightShelves(self, books, shelf_width):
        """
        :type books: List[List[int]]
        :type shelf_width: int
        :rtype: int
        """
        dp = [float('inf') for i in range(len(books))]
        dp[0] = books[0][1]
        for i in range(1,len(books)):
            current_height = 0
            temp = shelf_width
            j = i
            while j>=0 and temp-books[j][0]>=0:
                current_height = max(books[j][1],current_height)
                dp[i] = min(dp[i],current_height +( dp[j-1] if j-1 >=0 else 0))
                temp-=books[j][0]
                j-=1
        return dp[-1]

入力

[[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]]
4

出力

6