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若kw的话此时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]的情况且cost0特殊情况还可以令cost[i][houses[i]-1] 0;houses[i]0)Codeclass Solution { public: int minCost(vectorint houses, vectorvectorint cost, int m, int n, int target) { vectorvectorvectorint dp(m1, vectorvectorint(target 1, vectorint(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; } };Codeclass Solution { public: int minCost(vectorint houses, vectorvectorint cost, int m, int n, int target) { vectorvectorvectorint dp(m1, vectorvectorint(target 1, vectorint(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; } };