Hay una hilera de n casas, cada casa se puede pintar con uno de los tres colores: rojo, azul o verde. El costo de pintar cada casa con un color determinado es diferente. Tienes que pintar todas las casas de modo que no haya dos casas adyacentes del mismo color.
El costo de pintar cada casa con un color determinado está representado por una matriz de costos 3. Por ejemplo, costos[0][0] es el costo de pintar la casa 0 con color rojo; costos[1][2] es el costo de pintar la casa 1 con color verde, y así sucesivamente … Encuentre el costo mínimo para pintar todas las casas.
Solución Java
Un problema típico de DP.
public int minCost(int[][] costs) { if(costs==null||costs.length==0) return 0; for(int i=1; i<costs.length; i++){ costs[i][0] += Math.min(costs[i-1][1], costs[i-1][2]); costs[i][1] += Math.min(costs[i-1][0], costs[i-1][2]); costs[i][2] += Math.min(costs[i-1][0], costs[i-1][1]); } int m = costs.length-1; return Math.min(Math.min(costs[m][0], costs[m][1]), costs[m][2]); } |
O una forma diferente de escribir el código sin cambiar el valor original de la matriz.
public int minCost(int[][] costs) { if(costs==null||costs.length==0){ return 0; } int[][] matrix = new int[3][costs.length]; for(int j=0; j<costs.length; j++){ if(j==0){ matrix[0][j]=costs[j][0]; matrix[1][j]=costs[j][1]; matrix[2][j]=costs[j][2]; }else{ matrix[0][j]=Math.min(matrix[1][j-1], matrix[2][j-1])+costs[j][0]; matrix[1][j]=Math.min(matrix[0][j-1], matrix[2][j-1])+costs[j][1]; matrix[2][j]=Math.min(matrix[0][j-1], matrix[1][j-1])+costs[j][2]; } } int result = Math.min(matrix[0][costs.length-1], matrix[1][costs.length-1]); result = Math.min(result, matrix[2][costs.length-1]); return result; } |
