สมมติว่าเรามีบ้าน n หลังเรียงกัน แต่ละหลังทาสีได้ 1 ใน k สี ค่าใช้จ่ายในการทาแต่ละหลังด้วยสีแต่ละสีต่างกัน เราต้องทาทุกหลังโดยที่ไม่มีบ้านติดกันสีเหมือนกัน
ค่าใช้จ่ายแทนด้วยเมทริกซ์ n x k หาผลรวมค่าใช้จ่ายน้อยที่สุด
เช่น ถ้าอินพุตคือเมทริกซ์ 2x3: {{1,5,3},{2,9,4}} ผลลัพธ์จะเป็น 5 ทาบ้าน 0 สี 0, บ้าน 1 สี 2 ราคา 1+4=5 หรือ บ้าน 0 สี 2, บ้าน 1 สี 0 ราคา 3+2=5
ในการแก้ปัญหานี้ เราจะใช้ DP แบบ O(n*k) ทำตามขั้นตอน:
- สำหรับแต่ละบ้าน i=1..n-1: คำนวณ lmins[j] = min cost บ้านก่อนหน้าจนถึง j, rmins[j] = min cost บ้านก่อนหน้าจาก j ถึง 끝
- costs[i][j] += min(lmins[j-1], rmins[j+1]) (ข้ามสี j เอง)
- คำตอบคือ min ของ costs[n-1][*]
ตัวอย่าง
ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minCostII(vector>& costs) {
int n = costs.size(); int m = n ? costs[0].size() : 0; int ret = INT_MAX;
for(int i=1;i lmins(m), rmins(m);
lmins[0] = costs[i-1][0]; rmins[m-1] = costs[i-1][m-1];
for(int j=1;j=0;j--) rmins[j] = min(costs[i-1][j], rmins[j+1]);
for(int j=0;j=0 ? lmins[j-1] : INT_MAX;
int right = j+1> v = {{1,5,3},{2,9,4}};
cout << (ob.minCostII(v));
}
อินพุต
{{1,5,3},{2,9,4}}
เอาต์พุต
5
