C++实现房屋粉刷 II

假设我们有一排n栋房屋，每栋房屋都可以粉刷成k种颜色之一。每栋房屋粉刷成某种颜色的成本不同。我们需要粉刷所有房屋，并且相邻房屋的颜色不能相同。

每栋房屋粉刷成某种颜色的成本由一个n x k阶矩阵表示。我们需要找到粉刷所有房屋的最小成本。

例如，如果输入为：

则输出为5，因为将房屋0粉刷成颜色0，将房屋1粉刷成颜色2。最小成本为1 + 4 = 5；或者将房屋0粉刷成颜色2，将房屋1粉刷成颜色0。最小成本为3 + 2 = 5。

为了解决这个问题，我们将遵循以下步骤：

• n := costs矩阵的行数

• m := (如果n非零，则为costs矩阵的列数，否则为0)

• ret := inf (无限大)

• for i := 1 to n-1 do −

  • req := inf (无限大)

  • 定义一个大小为m的数组lmins

  • 定义一个大小为m的数组rmins

  • lmins[0] := costs[i - 1, 0]

  • rmins[m - 1] = costs[i - 1, m - 1]

  • for j := 1 to m-1 do −

    • lmins[j] := min(costs[i - 1, j], lmins[j - 1])

  • for j := m - 2 down to 0 do −

    • rmins[j] := min(costs[i - 1, j], rmins[j + 1])

  • for j := 0 to m-1 do −

    • left := (if j - 1 >= 0, then lmins[j - 1], otherwise inf)

    • right := (if j + 1 < m, then rmins[j + 1], otherwise inf)

    • costs[i, j] := costs[i, j] + min(left, right)

• for i := 0 to m-1 do −

  • ret := min(ret, costs[n - 1, i])

• return (if ret == inf, then 0, otherwise 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

Arnab Chakraborty

更新于：2020年7月21日

342 次浏览

开启你的职业生涯

完成课程获得认证

开始学习