Sword finger offer II 091 Paint the house

If there is a row of houses , common n individual , Every house can be painted red 、 One of the three colors blue or green , You need to paint all the houses and make the two adjacent houses not the same color .

Of course , Because the prices of different colors of paint on the market are different , So the cost of painting the house in different colors is different . The cost of painting each house in a different color is one  n x 3  Positive integer matrix of costs To represent the .

for example ,costs[0][0] It means the first one 0 The cost of painting the house red ;costs[1][2]  It means the first one 1 The cost of painting the house green , And so on .

Please calculate the minimum cost of painting all the houses .

Example 1：

Input : costs = [[17,2,17],[16,16,5],[14,3,19]]
Output : 10
explain : take 0 No. 1 house painted blue ,1 No. 1 house painted green ,2 No. 1 house painted blue .
     Minimum cost : 2 + 5 + 3 = 10.
Example 2：

Input : costs = [[7,6,2]]
Output : 2
 

Tips :

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

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/JEj789
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

1. Recurrence of violence （ Overtime ）

int min(int a,int b){
    return a<b?a:b;
}
//k What was the number of the last house painted 
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. Dynamic programming （

Execution time ：4 ms, In all  C  Defeated in submission 98.11% Users of

Memory consumption ：5.9 MB, In all  C  Defeated in submission 100.00% Users of

）

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. Dynamic programming （ For many colors ）

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;
}