大廠面試真題詳解：房屋染色

這裡有n個房子在一列直線上，現在我們需要給房屋染色，分别有紅色藍色和綠色。每個房屋染不同的顔色費用也不同，你需要設計一種染色方案使得相鄰的房屋顔色不同，并且費用最小，傳回最小的費用。

費用通過一個nx3 的矩陣給出，比如cost0表示房屋0染紅色的費用，cost1表示房屋1染綠色的費用。

線上評測位址：

領扣題庫官網 樣例 1:

輸入: [[14,2,11],[11,14,5],[14,3,10]]
輸出: 10
解釋: 第一個屋子染藍色，第二個染綠色，第三個染藍色，最小花費：2 + 5 + 3 = 10.           

樣例 2:

輸入: [[1,2,3],[1,4,6]]
輸出: 3           

算法：動态規劃(dp)

算法思路

• dpi表示第i幢房子塗j的顔色最小的花費總和，即從前一幢房子的狀态dp[i-1] k 中選一個不同顔色且最小的再加上給第i幢房子塗j顔色的costs。

代碼思路

1. 初始化狀态dp0=costs0
2. 從左往右周遊每一幢房子，計算到該幢房子塗每種顔色的最小花費，狀态轉移方程是dpi = min{dpi-1 +costsi} (k != j)
3. 答案為到最後一幢房子塗每種顔色花費中的最小值，即min(dpn-1),k=0,1,2

複雜度分析

N表示房子的幢數，即costs數組長度

• 空間複雜度：O(1)

• 時間複雜度：O(N)

  優化

• 滾動存儲狀态，可以将空間複雜度從O(N)優化到O(1)。

代碼

public class Solution {

    /**
     * @param costs: n x 3 cost matrix
     * @return: An integer, the minimum cost to paint all houses
     */

    public int minCost(int[][] costs) {
        int n = costs.length;
        if (n == 0) {
            return 0;
        }

        //dp[i][j]表示第i幢房子塗j的顔色最小的總和
        //初始化狀态dp[0][i]=costs[0][i]

        int[][] dp = new int[2][3];

        for (int i= 0; i < 3; i++) {
            dp[0][i] = costs[0][i];
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                dp[i&1][j] = Integer.MAX_VALUE;
                for (int k = 0; k < 3; k++) {
                    if (k != j) {
                        dp[i&1][j] = Math.min(dp[i&1][j], dp[i&1^1][k] + costs[i][j]);
                    }
                }
            }
        }
        return Math.min(dp[n&1^1][0], Math.min(dp[n&1^1][1], dp[n&1^1][2]) );
    }
}           

更多題解參考：

九章官網solution