題目

一排n幢房子要粉刷成紅色、綠色和藍色，不同房子被粉刷成不同顏色的成本不同。用一個n×3的數(shù)組表示n幢房子分別用3種顏色粉刷的成本。要求任意相鄰的兩幢房子的顏色都不一樣，請計算粉刷這n幢房子的最少成本。例如，粉刷3幢房子的成本分別為[[17，2，16]，[15，14，5]，[13，3，1]]，如果分別將這3幢房子粉刷成綠色、藍色和綠色，那么粉刷的成本是10，是最少的成本。

分析：確定狀態(tài)轉(zhuǎn)移方程

用i表示房子，f(顏色)(i)表示最小花費，costs[][]表示當(dāng)前房子當(dāng)前顏色的話費
f(顏色)(i) = Math.min( f(其他顏色)(i-1) , f(其他顏色)(i-1) ) + costs[當(dāng)前房子][當(dāng)前顏色]

解

public class Test {public static void main(String[] args) {int[][] costs = {{17, 2, 16},{15, 14, 5},{13, 3, 1}};int result = minCost(costs);System.out.println(result);}public static int minCost(int[][] costs) {if (costs.length == 0) {return 0;}// 3:需要記錄3種顏色的花費// 2:只需要記錄上一棟房子和當(dāng)前房子的花費int[][] dp = new int[3][2];for (int j = 0; j < 3; j++) {// 記錄第一棟房子3中顏色的花費dp[j][0] = costs[0][j];}for (int i = 1; i < costs.length; i++) {// 遍歷房子for (int j = 0; j < 3; j++) {// 遍歷顏色// [(j+2)%3]：其他顏色的意思// [(i-1)%2]：上一棟房子的意思int prev1 = dp[(j + 2) % 3][(i - 1) % 2];int prev2 = dp[(j + 1) % 3][(i - 1) % 2];dp[j][i % 2] = Math.min(prev1, prev2) + costs[i][j];}}int last = (costs.length - 1) % 2;// 最后的房子// dp[0][last]、dp[1][last]、dp[2][last]：表示3種顏色，取最小值return Math.min(dp[0][last], Math.min(dp[1][last], dp[2][last]));}}