剑指offer II 091.粉刷房子

假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。

例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。

请计算出粉刷完所有房子最少的花费成本。

示例 1：

输入: costs = [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
     最少花费: 2 + 5 + 3 = 10。
示例 2：

输入: costs = [[7,6,2]]
输出: 2
 

提示:

costs.length == n
costs[i].length == 3
1 <= n <= 100
1 <= costs[i][j] <= 20

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/JEj789
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1.暴力递归（超时）

int min(int a,int b){
    return a<b?a:b;
}
//k为上一个粉刷的房子是几号
int f(int** costs,int row,int col,int idx,int k)
{
    if(idx==row){
        return 0;
    }
    int p1,p2,p3;
    p1=p2=p3=100000000;

    if(k!=0){
        p1=costs[idx][0]+f(costs,row,col,idx+1,0);
    }
    if(k!=1){
        p2=costs[idx][1]+f(costs,row,col,idx+1,1);
    }
    if(k!=2){
        p3=costs[idx][2]+f(costs,row,col,idx+1,2);
    }
    return min(p1,min(p2,p3));
}
int minCost(int** costs, int costsSize, int* costsColSize){
    return f(costs,costsSize,*costsColSize,0,-1);
}

2.动态规划（

执行用时：4 ms, 在所有 C 提交中击败了98.11%的用户

内存消耗：5.9 MB, 在所有 C 提交中击败了100.00%的用户

）

int min(int a,int b){
    return a<b?a:b;
}
int minCost(int** costs, int costsSize, int* costsColSize){
    int dp[costsSize][*costsColSize];
    memset(dp,0,sizeof(dp));
    dp[0][0]=costs[0][0];
    dp[0][1]=costs[0][1];
    dp[0][2]=costs[0][2];

    for(int idx=1;idx<costsSize;idx++){
        for(int k=0;k<*costsColSize;k++){
            if(k==0){
                dp[idx][k]=min(dp[idx-1][1],dp[idx-1][2])+costs[idx][k];
            }
            if(k==1){
                dp[idx][k]=min(dp[idx-1][0],dp[idx-1][2])+costs[idx][k];
            }
            if(k==2){
                dp[idx][k]=min(dp[idx-1][0],dp[idx-1][1])+costs[idx][k];
            }
        }
    }
    int ans = min(dp[costsSize-1][0],min(dp[costsSize-1][1],dp[costsSize-1][2]));
    return ans;
}

3.动态规划（针对很多种颜色）

int min(int a,int b){
    return a<b?a:b;
}
int minCost(int** costs, int costsSize, int* costsColSize){
    int dp[costsSize][*costsColSize];
    memset(dp,0,sizeof(dp));
    dp[0][0]=costs[0][0];
    dp[0][1]=costs[0][1];
    dp[0][2]=costs[0][2];

    for(int idx=1;idx<costsSize;idx++){
        for(int k=0;k<*costsColSize;k++){
            int m = 10000000;
            for(int t=0;t<*costsColSize;t++){
                if(t!=k){
                    m=min(m,dp[idx-1][t]);
                }
            }
            dp[idx][k]=costs[idx][k]+m;
        }
    }
    int ans = dp[costsSize-1][0];
    for(int i=1;i<*costsColSize;i++){
        ans = min(ans,dp[costsSize-1][i]);
    }
    return ans;
}