Hay una hilera de n casas, cada casa se puede pintar con uno de los k colores. El costo de pintar cada casa con un color determinado es diferente. Tienes que pintar todas las casas de manera 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 ansk. Por ejemplo, costos[0][0] es el costo de pintar la casa 0 con el color 0; costos[1][2] es el costo de pintar la casa 1 con el color 2, y así sucesivamente … Encuentre el costo mínimo para pintar todas las casas.
Solución Java
public int minCostII(int[][] costs) { if(costs==null || costs.length==0) return 0; int preMin=0; int preSecond=0; int preIndex=-1; for(int i=0; i<costs.length; i++){ int currMin=Integer.MAX_VALUE; int currSecond = Integer.MAX_VALUE; int currIndex = 0; for(int j=0; j<costs[0].length; j++){ if(preIndex==j){ costs[i][j] += preSecond; }else{ costs[i][j] += preMin; } if(currMin>costs[i][j]){ currSecond = currMin; currMin=costs[i][j]; currIndex = j; } else if(currSecond>costs[i][j] ){ currSecond = costs[i][j]; } } preMin=currMin; preSecond=currSecond; preIndex =currIndex; } int result = Integer.MAX_VALUE; for(int j=0; j<costs[0].length; j++){ if(result>costs[costs.length-1][j]){ result = costs[costs.length-1][j]; } } return result; } |
