[LeetCode][DP] 265. Paint House

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;
    }
};