256 Paint House

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.

Note: All costs are positive integers.

分析

输入：一个能代表花费的二维数组cost[][]

输出：最小花费 int minCost

思路1：recursion

1.定义递归函数：OPT()

第一个限制：总花费最小－－－》id：从0到id的房子

第二个限制：相邻不能同色－－－》color：第id个房子涂color色

OPT(id, color)：0至第id个房子且第id个房子涂color色时最低的花费

2.递归公式：

OPT(id, 0) = min{ OPT(id-1,1) + cost[id][0], OPT(id-1,2) + cost[id][0]}

OPT(id, 1) = min{ OPT(id-1,0) + cost[id][0], OPT(id-1,2) + cost[id][0]}

OPT(id, 2) = min{ OPT(id-1,0) + cost[id][0], OPT(id-1,1) + cost[id][0]}

3.输出

minCost = min{OPT(n-1, 0), OPT(n-1, 1), OPT(n-1, 2)}

其中n是房子的数量

思路1实现中遇到的问题

1.递归函数minCostHelper(int id, int color)的定义

由于递归函数中需要用到cost[][],因此考虑要不要把cost当作递归函数一个参数传进去。其实可以更简便的方法是，设一对于class的instance variable，在主方法中进行赋值，因此递归函数也可以用。

2.递归函数中如何设计根据color的值来得出另两个

1）取余运算：（color＋1）％3 与（color－1）％3

但是在实现中会ava.lang.StackOverflowError（有待解决）

2）if语句简单粗暴

3.如何比较3个数的大小

1）if语句简单粗暴

    //return min{x,y,z};
    if(x <= y && x <= z) return x;
    if(y <= x && y <= z) return y;
    return z;

注意：一定要是<=而不是<，这样要是x＝y<z时，结果才能正确！！！

思路1代码

public class Solution {

    private int[][] costs;

    public int minCost(int[][] costs) {

    this.costs = costs;
    int n = costs.length;

    if(n == 0) return 0;

    int x = minCostHelper(n-1,0);
    int y = minCostHelper(n-1,1);
    int z = minCostHelper(n-1,2);

    //return min{x,y,z};
    if(x <= y && x <= z) return x;
    if(y <= x && y <= z) return y;
    return z;


    }

    private int minCostHelper(int id, int color) {

    int min = 0;
    //base case
    if(id == 0 && color == 0) return min = costs[0][0];
    if(id == 0 && color == 1) return min = costs[0][1];
    if(id == 0 && color == 2) return min = costs[0][2];

    int m,n;
    //recursive
    if(color == 0) {
        m = 1;
        n = 2;
    }else if(color == 1) {
        m = 0;
        n = 2;
    }else {
        m = 0;
        n = 1;
    }
    int a = minCostHelper(id-1,m) + costs[id][color];
    int b = minCostHelper(id-1,n) + costs[id][color];

    if( a < b ) min = a;
    else min = b;

    return min;
    }
}

思路1结果：Time limit Exceeded

原因是只采用了递归，相当于是从树的root往下计算，每条支路的每一个节点都会重新计算，因此不同支路的计算中会进行多次重复计算，运算复杂O(n^2)--Exponential!

思路2: 对递归进行修改，增加Memo[ ][ ]——DP

此时运用递归函数从Memo[ ][ ]的低端开始计算，之后的Memo值用之前已经计算的值（如果有的话），如果没有，用递归函数算。

//主方法
for i from 0 to n-1:
    Memo[i][0] = minCostHelper(i, 0);
    Memo[i][1] = minCostHelper(i, 1);
    Memo[i][1] = minCostHelper(i, 1);
endfor

minCost ＝ min｛Memo[n-1][0],Memo[n-1][1],Memo[n-1][2]｝

//递归函数
    //base case
    if i==0 and color==0/1/2:
        Memo[0][0/1/2] = cost[0][0/1/2];
    endif

    //recursive
    if Memo[id][color] == 0:
        Memo[id][color] = min{Memo[id-1][color1] + cost[id][color], Memo[id-1][~color2] + cost[id][color]};
        return Memo[id][color]
    else:
        return Memo[id][color];

思路2实现中的问题

1.Memo[][]怎么建，在哪建

设一个instance variable的索引让递归函数能用，在主方法中根据cost的长度对索引赋值。

AC CODE

//jiayuanh_0201: 3 ms, Your runtime beats 12.86% of java submissions.
public class Solution {

    private int[][] costs;
    private int[][] Memo;

    public int minCost(int[][] costs) {

        this.costs = costs;
        int n = costs.length;
        this.Memo = new int[n][3];

        //corner case
        if(n == 0) return 0;

        //general case
        for(int i=0; i<n; i++) {

            Memo[i][0] = minCostHelper(i,0);
            Memo[i][1] = minCostHelper(i,1);
            Memo[i][2] = minCostHelper(i,2);

        }

        if((Memo[n-1][0] <= Memo[n-1][1]) && (Memo[n-1][0] <= Memo[n-1][2])) {
            return Memo[n-1][0];
        } else if ((Memo[n-1][1] <= Memo[n-1][0]) && (Memo[n-1][1] <= Memo[n-1][2])) {
            return Memo[n-1][1];
        } else {
            return Memo[n-1][2];
        }
    }

    private int minCostHelper(int id, int color) {

        int min = 0;
        //base case
        if(id == 0 && color == 0) {
            Memo[0][0] = costs[0][0];
            return Memo[0][0];
        }
        if(id == 0 && color == 1) {
            Memo[0][1] = costs[0][1];
            return Memo[0][1];
        }
        if(id == 0 && color == 2) {
            Memo[0][2] = costs[0][2];
            return Memo[0][2];
        }

        //recursive
        if(Memo[id][color] == 0) {
            int m,n;
            if(color == 0) {
            m = 1;
            n = 2;
            } else if(color == 1) {
            m = 0;
            n = 2;
            } else {
            m = 0;
            n = 1;
            }

            int a = minCostHelper(id-1,m) + costs[id][color];
            int b = minCostHelper(id-1,n) + costs[id][color];

            if( a < b ) {
            Memo[id][color] = a;
            }
            else {
            Memo[id][color] = b;
            }
            return Memo[id][color];
        } else {
            return Memo[id][color];
        } 

    }
}