C++でのペイントハウスII

n個の家が並んでいるとすると、各家はk色のいずれかでペイントできます。特定の色の家ごとの塗装費は異なります。ここで、隣接する2つの家が同じ色にならないように、すべての家をペイントする必要があることに注意する必要があります。

各家を特定の色で塗るコストは、次数nxkの行列で表されます。そして、すべての家を塗装するための最小コストを見つける必要があります。

したがって、入力が次のような場合

この場合、出力は5になります。ペイントハウス0をカラー0に、ペイントハウス1をカラー2にすると、最小コストは1 + 4=5になります。または、ハウス0をカラー2にペイントし、ハウス1をカラー0にペイントします。最小コストは3 + 2=5です。

これを解決するには、次の手順に従います-

• n：=コストの行サイズ

• m：=（nがゼロ以外の場合、コストの列サイズ、それ以外の場合は0）

• ret：=inf

• 初期化i：=1の場合、i

  • req：=inf

  • サイズmの配列lminsを定義します

  • サイズmの配列rminsを定義します

  • lmins [0]：=コスト[i-1、0]

  • rmins [m-1]=コスト[i-1、m-1]

  • 初期化j：=1の場合、j

    • lmins [j]：=最小コスト[i-1、j]およびlmins [j-1]

  • 初期化j：=m-2の場合、j> =0の場合、更新（jを1つ減らす）、実行-

    • rmins [j]：=最小コスト[i-1、j]およびrmins [j + 1]

  • 初期化j：=0の場合、j

    • left：=（j-1> =0の場合、lmins [j-1]、それ以外の場合はinf）

    • right：=（j + 1

    • コスト[i、j]：=コスト[i、j] + min（左、右）

• 初期化i：=0の場合、i

  • ret：=retとコストの最小値[n-1、i]

• return（retがinfと同じ場合は0、それ以外の場合はret）

例

理解を深めるために、次の実装を見てみましょう-

#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