leetcode 困难题 1473. Paint House III 粉刷房子 III

Problem: 1473. Paint House III 粉刷房子 III

动态规划的呢，dp[i][j][k]表示前i个houses、共j个邻居、第i个house粉刷的颜色k

初始条件是：若houses[0]!=0则dp[1][1][houses[0]] = 0; 否则 dp[1][1][k] = cost[0][k-1];

三重基本循环的，j的上界是：r = min(i, target);

递推公式是这个：也就是k和w不相同，则拿到最小值 dp[i-1][j-1][w]，第i-1个house粉刷颜色w，若k==w的话此时j不变。最后累加上当前需要付出的dp[i][j][k] += cost[i-1][k-1];

if(k!=w) dp[i][j][k] = min(dp[i-1][j-1][w], dp[i][j][k]);

else dp[i][j][k] = min(dp[i-1][j][w], dp[i][j][k]);

特殊情况是：houses[i-1] > 0，此时只需要考虑 kk = houses[i-1]的情况，且cost=0

特殊情况还可以令：cost[i][houses[i]-1] = 0;（houses[i]>0)

Code

class Solution {
public:
int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
vector<vector<vector<int>>> dp(m+1, vector<vector<int>>(target + 1, vector<int>(n + 1, INT_MAX/10)));
int r, cnt = 0;
if(houses[0]!= 0) {
cnt++;
dp[1][1][houses[0]] = 0;
}
else for(int k = 1; k <= n; k++) dp[1][1][k] = cost[0][k-1];
int kk;
for(int i = 2; i <= m; i++) {
r = min(i, target);
for(int j = 1; j <= r; j++) {
if(houses[i-1] > 0) {
kk = houses[i-1];
for(int w = 1; w <= n; w++) {
if(kk!=w) dp[i][j][kk] = min(dp[i-1][j-1][w], dp[i][j][kk]);
else dp[i][j][kk] = min(dp[i-1][j][w], dp[i][j][kk]);
}
continue;
}
for(int k = 1; k <= n; k++) {
for(int w = 1; w <= n; w++) {
if(k!=w) dp[i][j][k] = min(dp[i-1][j-1][w], dp[i][j][k]);
else dp[i][j][k] = min(dp[i-1][j][w], dp[i][j][k]);
}
dp[i][j][k] += cost[i-1][k-1];
}
}
}
int mx = *min_element(dp[m][target].begin(), dp[m][target].end());
if(mx==(INT_MAX/10)) return -1;
return mx;
}
};

Code

class Solution {
public:
int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
vector<vector<vector<int>>> dp(m+1, vector<vector<int>>(target + 1, vector<int>(n + 1, INT_MAX/10)));
int r, cnt = 0;
if(houses[0]!= 0) {
cnt++;
dp[1][1][houses[0]] = 0;
}
else for(int k = 1; k <= n; k++) dp[1][1][k] = cost[0][k-1];
bool a;
for(int i = 0; i < m; i++) {
a = houses[i] > 0;
if(a) {
for(int k = 0; k < n; k++) {
cost[i][k] = INT_MAX/10;
}
cost[i][houses[i]-1] = 0;
}
}
for(int i = 2; i <= m; i++) {
r = min(i, target);
for(int j = 1; j <= r; j++) {
for(int k = 1; k <= n; k++) {
for(int w = 1; w <= n; w++) {
if(k!=w) dp[i][j][k] = min(dp[i-1][j-1][w] + cost[i-1][k-1], dp[i][j][k]);
else dp[i][j][k] = min(dp[i-1][j][w] + cost[i-1][k-1], dp[i][j][k]);
}
}
}
}
int mx = *min_element(dp[m][target].begin(), dp[m][target].end());
if(mx==(INT_MAX/10)) return -1;
return mx;
}
};