博文中会简要介绍Leetcode P0256题目分析及解题思路。

“Paint House”是一道中等难度的题目，主要思路是使用动态规划算法来解答。

There is a row of n houses, where each house can be painted one of 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 an n x 3 cost matrix costs.

For example, costs[0][0] is the cost of painting house 0 with the color red; costs[1][2] is the cost of painting house 1 with color green, and so on…

Return the minimum cost to paint all houses.

这道题的动态规划思路比较直接，递推式如下，

令dp[i][3]为第i个房子分别涂指定颜色后，前i个房子的最小开销。

dp[i][0] = min(dp[i-1][1], dp[i-1][2])
dp[i][1] = min(dp[i-1][0], dp[i-1][2])
dp[i][2] = min(dp[i-1][0], dp[i-1][1])

cost = min(dp[i][0], dp[i][1], dp[i][2])，此为最终的前i个房子涂色的最小开销。

简单来说，当第i个房子涂某一种颜色时，由于前一个房子只能涂与它不一样的颜色，所以此时前i个房子涂色的最小开销取决于第i-1个房子涂另外两种颜色时前i-1个房子的涂色开销中的最小值。以此类推即可。

以下是Java的题解代码实现。

class Solution {
    public int minCost(int[][] costs) {
        int N = costs.length;
        int[][] dp = new int[N][3];
        // Cost of the first house in three colors
        dp[0] = costs[0];
        
        int minCost = Math.min(Math.min(dp[0][0], dp[0][1]), dp[0][2]);
        // Dynamic Programming
        for (int i=1; i<N; ++i) {
            dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2])+costs[i][0];
            dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2])+costs[i][1];
            dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1])+costs[i][2];
            
            minCost = Math.min(Math.min(dp[i][0], dp[i][1]), dp[i][2]);
        }
        
        return minCost;
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int N = costs.size();
        vector<vector<int>> dp(N, vector<int>(3, 0));
        // Assign the first house's cost
        dp[0] = costs[0];
        
        int min_cost = min(dp[0][0], min(dp[0][1], dp[0][2]));
        for (int i=1; i<N; ++i) {
            dp[i][0] = min(dp[i-1][1], dp[i-1][2])+costs[i][0];
            dp[i][1] = min(dp[i-1][0], dp[i-1][2])+costs[i][1];
            dp[i][2] = min(dp[i-1][0], dp[i-1][1])+costs[i][2];
            
            min_cost = min(dp[i][0], min(dp[i][1], dp[i][2]));
        }
        
        return min_cost;
    }
};