資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++實現房屋粉刷 II
假設我們有一排n棟房屋，每棟房屋都可以粉刷成k種顏色之一。每棟房屋粉刷成某種顏色的成本不同。我們需要粉刷所有房屋，並且相鄰房屋的顏色不能相同。
每棟房屋粉刷成某種顏色的成本由一個n x k階矩陣表示。我們需要找到粉刷所有房屋的最小成本。
例如，如果輸入為：
| 1 | 5 | 3 |
| 2 | 9 | 4 |
則輸出為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
342 次瀏覽
