C++で解く「ペイントハウスII」問題：隣接する家を同じ色にしないための最小コスト計算

ペイントハウスII問題とは

n軒の家が一列に並んでいるとします。各家はk色の中から1色を選んで塗ることができますが、色ごとに塗布コストが異なります。ここで守らなければならない条件は、隣り合う家同士が同じ色にならないように、すべての家を塗るということです。

各家を特定の色で塗るときのコストは、n×kの行列として与えられます。このとき、すべての家を塗るために必要な最小コストを求めるのがこの問題の目的です。

例えば、入力が次のような場合を考えてみましょう。

この場合の出力は5になります。家0を色0で塗り、家1を色2で塗れば、最小コストは1 + 4 = 5です。あるいは、家0を色2で、家1を色0で塗っても、3 + 2 = 5となり、同じ結果が得られます。

解法のアプローチ

この問題は動的計画法（DP）で解けます。単純に前の行の最小値をそのまま使うと、隣接禁止の制約に違反する可能性があります。そこで役立つのが、以下の2つの補助配列です。

• lmins（左からの累積最小値）：各行について、左端から順に「その位置までの最小コスト」を記録します。
• rmins（右からの累積最小値）：右端から逆順に「その位置までの最小コスト」を記録します。

この2つを組み合わせることで、各セルに対して「自分以外の色の中での最小コスト」をO(1)で参照でき、全体の計算量をO(n×k)に抑えられます。

アルゴリズムの手順

• n := costs の行数とする
• m := （n が 0 でなければ costs の列数、そうでなければ 0）
• ret := 無限大（INT_MAX）
• i := 1 から n-1 まで繰り返し：
  • req := 無限大
  • サイズ m の配列 lmins を定義する
  • サイズ m の配列 rmins を定義する
  • lmins[0] := costs[i - 1][0]
  • rmins[m - 1] := costs[i - 1][m - 1]
  • j := 1 から m-1 まで：lmins[j] := min(costs[i - 1][j], lmins[j - 1])
  • j := m-2 から 0 まで（逆順）：rmins[j] := min(costs[i - 1][j], rmins[j + 1])
  • j := 0 から m-1 まで：
    • left := （j - 1 >= 0 なら lmins[j - 1]、それ以外は無限大）
    • right := （j + 1 < m なら rmins[j + 1]、それ以外は無限大）
    • costs[i][j] := costs[i][j] + min(left, right)
• i := 0 から m-1 まで：ret := min(ret, costs[n - 1][i])
• ret が無限大と等しければ 0 を、そうでなければ ret を返す

C++による実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minCostII(vector<vector<int>>& costs) {
      int n = costs.size();
      int m = n ? costs[0].size() : 0;
      int ret = INT_MAX;
      for (int i = 1; i < n; i++) {
         int req = INT_MAX;
         vector<int> lmins(m);
         vector<int> rmins(m);
         lmins[0] = costs[i - 1][0];
         rmins[m - 1] = costs[i - 1][m - 1];
         for (int j = 1; j < m; j++) {
            lmins[j] = min(costs[i - 1][j], lmins[j - 1]);
         }
         for (int j = m - 2; j >= 0; j--) {
            rmins[j] = min(costs[i - 1][j], rmins[j + 1]);
         }
         for (int j = 0; j < m; j++) {
            int left = j - 1 >= 0 ? lmins[j - 1] : INT_MAX;
            int right = j + 1 < m ? rmins[j + 1] : INT_MAX;
            costs[i][j] += min(left, right);
         }
      }
      for (int i = 0; i < m; i++) {
         ret = min(ret, costs[n - 1][i]);
      }
      return ret == INT_MAX ? 0 : ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{1,5,3},{2,9,4}};
   cout <<(ob.minCostII(v));
}

入力

{{1,5,3},{2,9,4}}

出力

5

まとめ

ペイントハウスII問題では、隣接する家が同じ色にならないという制約があるため、単純な最小値の追跡だけでは不十分です。左方向・右方向それぞれからの累積最小値配列（lmins・rmins）を用意することで、「自分以外の色の最小コスト」を効率よく取得でき、時間計算量O(n×k)、空間計算量O(k)で最適解を求められます。