paint-house

Paint House – LeetCode 256

Problem

Description

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. 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 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on… Find the minimum cost to paint all houses.

Answer

Original

Code

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size();
        if(n==0) return 0;
        for(int i=1; i<n; ++i){
            for(int j=0; j<3; ++j){
                costs[i][j] += min(costs[i-1][(j+1)%3], costs[i-1][(j+2)%3]);
            }
        }
        return min(costs[n-1][0], min(costs[n-1][1], costs[n-1][2]));
    }
};

思路

使用DP,递归式是costs[i][j] == costs[i][j] + min(costs[i-1][(j+1)%3], costs[i-1][(j+2)%3])，就是下一个颜色由上一个方案的两个可选颜色中选出，最后从三个最终方案中选出最终的最优答案，妙。时间复杂度$O(n)$，空间复杂度$O(1)$。

Better

思路

还没看到更好的思路。