สมมุติว่าเรามีบ้านติดกัน 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 :=ขนาดแถวของต้นทุน
-
m :=(ถ้า n ไม่ใช่ศูนย์ ให้กำหนดขนาดของต้นทุน มิฉะนั้น 0)
-
ret :=inf
-
สำหรับการเริ่มต้น i :=1 เมื่อฉัน
-
req :=inf
-
กำหนดอาร์เรย์ lmins ขนาด m
-
กำหนดขนาดอาร์เรย์ rms
-
lmins[0] :=cost[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
-
ซ้าย :=(ถ้า j - 1>=0 แล้ว lmins[j - 1] มิฉะนั้น inf)
-
right :=(ถ้า j + 1
-
ค่าใช้จ่าย[i, j] :=ค่าใช้จ่าย[i, j] + นาที(ซ้าย, ขวา)
-
-
-
สำหรับการเริ่มต้น 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
