[LeetCode][DP] 265. Paint House II

Problem

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Follow up:
Could you solve it in O(nk) runtime?

Solution

class Solution {
public:
    int minCostII(vector<vector<int>>& costs) {
        if (costs.size() == 0) {
            return 0;
        }
        
        vector<vector<int>> f(2, vector<int>(costs[0].size())); // 滚动数组
        
        for(int i = 0; i < costs[0].size(); i++) {
            f[0][i] = costs[0][i];
        }
        
        for(int i = 1; i < costs.size(); i++) {
            int index = i % 2;
            for(int j = 0; j < costs[i].size(); j++) {
                f[index][j] = INT_MAX;
                for(int k = 0; k < costs[i].size(); k++) {
                    if (j != k) { // 确保当前选的颜色和前一个颜色不一样
                        f[index][j] = min(f[index][j], f[1-index][k] + costs[i][j]);
                    }
                }
            }
        }
        
        int minCost = INT_MAX;
        int index = (costs.size() - 1) % 2;
        for(int i = 0; i < costs[costs.size() - 1].size(); i++) {
            minCost = min(minCost, f[index][i]);
        }
        
        return minCost;
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容