房屋染色

房屋染色

题目：
这里有n个房子在一列直线上，现在我们需要给房屋染色，分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同，你需要设计一种染色方案使得相邻的房屋颜色不同，并且费用最小，返回最小的费用。

费用通过一个nx3 的矩阵给出，比如cost[0][0]表示房屋0染红色的费用，cost[1][2]表示房屋1染绿色的费用。

样例
样例 1:

输入: [[14,2,11],[11,14,5],[14,3,10]]
输出: 10
解释: 第一个屋子染蓝色，第二个染绿色，第三个染蓝色，最小花费：2 + 5 + 3 = 10.
样例 2:

输入: [[1,2,3],[1,4,6]]
输出: 3

解题思路：首先想最后一个房屋应该涂什么颜色最便宜，确定了最后一个房子的颜色后要思考倒数第二个房子的颜色，以此类推这是一个重复子问题，但是确定当前房子时需要知道之前的房子是什么颜色，所以需要多开一维数组来对颜色进行记录

public class Solution {
    /**
     * @param costs: n x 3 cost matrix
     * @return: An integer, the minimum cost to paint all houses
     */
    public int minCost(int[][] costs) {
        //数组定义：dp[i][j]表示第i栋房子涂j种涂料时的最小花费
        int dp[][] = new int[costs.length + 1][3];
        
        //初始化
        dp[0][0] = 0;
        dp[0][1] = 0;
        dp[0][2] = 0;
        
        /**
        状态方程 dp[i][j] = min(dp[i - 1][0..2] + costs[i][j])
        **/
        
        for(int i = 1; i <= costs.length; i++) {
            for(int j = 0; j < 3; j++) {
                for(int k = 0; k < 3; k++) {
                    if(k == j) continue;
                    if(dp[i][j] != 0)
                        dp[i][j] = Math.min(dp[i - 1][k] + costs[i - 1][j], dp[i][j]);
                        
                    else {
                        dp[i][j] = dp[i - 1][k] + costs[i - 1][j];
                    }
                }
            }
        }
        
        return Math.min(dp[costs.length][0], Math.min(dp[costs.length][1],dp[costs.length][2]));
    }
}