这里有 n 个房子在一列直线上，现在我们需要给房屋染色，分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同，你需要设计一种染色方案使得相邻的房屋颜色不同，并且费用最小，返回最小的费用。 费用通过一个 nx3 的矩阵给出，比如 cost[0][0]表示房屋 0 染红色的费用，cost[1][2]表示房屋 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)

算法思路

• dp[i][j]表示第 i 幢房子涂 j 的颜色最小的花费总和，即从前一幢房子的状态 dp[i-1][k] (k != j)中选一个不同颜色且最小的再加上给第 i 幢房子涂 j 颜色的 costs 。

代码思路

1. 初始化状态 dp[0][i]=costs[0][i]
2. 从左往右遍历每一幢房子，计算到该幢房子涂每种颜色的最小花费，状态转移方程是 dp[i][j] = min{dp[i-1][k] +costs[i][j]} (k != j)
3. 答案为到最后一幢房子涂每种颜色花费中的最小值，即 min(dp[n-1][k]),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]) );     } } 

大佬有話說 (0)