Leetcode: 【每日一题】- 2020-02-05 - 🔒256. 粉刷房子

[azl397985856]

假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的矩阵来表示的。

例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。请你计算出粉刷完所有房子最少的花费成本。

注意：

所有花费均为正整数。

示例：

输入: [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
  最少花费: 2 + 5 + 3 = 10。

题目地址： https://leetcode-cn.com/problems/paint-house/

[ZHAOXIN009]

C++
Runtime: 8 ms, faster than 76.16% of C++ online submissions for Paint House.
Memory Usage: 9.7 MB, less than 100.00% of C++ online submissions for Paint House.

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        if(costs.empty())return 0;
        for(int i=1; i<costs.size(); ++i){
            for(int j=0; j<3; ++j){
                int mincost=INT_MAX;
                for(int k=0; k<3; ++k){
                    if(j==k)continue;
                    mincost=min(mincost, costs[i-1][k]);
                }
                costs[i][j]+=mincost;
            }
        }
        int bottom=costs.size()-1;
        int res=INT_MAX;
        for(int i=0 ; i<3; ++i){
            res=min(res,costs[bottom][i]);
        }
        return res;
    }
};

[azl397985856]

@ZHAOXIN009 我解释一下楼上的代码。

楼上的算法本质上是DP dp[i][j] 表示的是第i个房子如果涂第j个颜色的话的最小值。其中j的取值范围是0，1，2，分别表示三种颜色。

内部两层循环由于是常数项，因此总的时间复杂度还是$O(N)$。实际上最后的res也可以放到上面的的循环一并求出。换句话说，res只是上述生成dp数组的一个副产物。

内层循环的基本逻辑是，我们两两组合三种颜色，一共是3*3=9种情况，我们排除3种相同颜色的情况，也就是六种情况，我们求出六种种的最小值更新到dp[i][j]即可。

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.