Medium

题目描述

给你一个表示房子数量的偶数 n，这些房子排成一条直线，以及一个大小为 n x 3 的二维数组 cost，其中 cost[i][j] 表示用颜色 j + 1 粉刷房子 i 的成本。

如果房子满足以下条件，它们就会看起来很美观：

  • 没有两个相邻的房子被涂成相同的颜色。
  • 与行两端等距的房子不被涂成相同的颜色。例如，如果 n = 6，位置 (0, 5)、(1, 4) 和 (2, 3) 的房子被认为是等距的。

返回使房子看起来美观的最小粉刷成本。

示例 1：

输入: n = 4, cost = [[3,5,7],[6,2,9],[4,8,1],[7,3,5]]
输出: 9
解释: 最优的粉刷序列是 [1, 2, 3, 2]，对应成本 [3, 2, 1, 3]。

示例 2：

输入: n = 6, cost = [[2,4,6],[5,3,8],[7,1,9],[4,6,2],[3,5,7],[8,2,4]]
输出: 18
解释: 最优的粉刷序列是 [1, 3, 2, 3, 1, 2]，对应成本 [2, 8, 1, 2, 3, 2]。

约束条件：

  • 2 <= n <= 10^5
  • n 是偶数
  • cost.length == n
  • cost[i].length == 3
  • 0 <= cost[i][j] <= 10^5

解题思路

这道题需要满足两个约束条件：相邻房子颜色不同，对称位置房子颜色不同。

核心思路：

  1. 由于对称约束，我们可以将问题分解为处理房子对：(0,n-1), (1,n-2), …, (n/2-1, n/2)
  2. 对于每一对对称房子，我们需要选择两种不同的颜色
  3. 同时要保证相邻房子（包括对称房子之间的相邻关系）颜色不同

动态规划方法：

  • 状态定义：dp[i][c1][c2] 表示处理完前 i 对房子，第 i-1 对的颜色为 (c1, c2) 时的最小成本
  • 状态转移：枚举当前对的所有有效颜色组合，确保与前一对不冲突
  • 有效性检查：对于第 i 对房子 (i, n-1-i)，颜色 (c1, c2) 需要满足：
    • c1 != c2（对称约束）
    • 与相邻位置的颜色不同（相邻约束）

优化： 由于只有3种颜色，我们可以枚举所有9种颜色组合，通过预处理有效组合来优化。

时间复杂度为 O(n)，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    long long minCost(int n, vector<vector<int>>& cost) {
        vector<pair<int, int>> validPairs;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i != j) {
                    validPairs.push_back({i, j});
                }
            }
        }
        
        vector<long long> dp(6, LLONG_MAX);
        
        // Initialize first pair
        for (int k = 0; k < 6; k++) {
            int c1 = validPairs[k].first, c2 = validPairs[k].second;
            dp[k] = cost[0][c1] + cost[n-1][c2];
        }
        
        for (int i = 1; i < n/2; i++) {
            vector<long long> newDp(6, LLONG_MAX);
            
            for (int k = 0; k < 6; k++) {
                int c1 = validPairs[k].first, c2 = validPairs[k].second;
                long long currentCost = cost[i][c1] + cost[n-1-i][c2];
                
                for (int prev = 0; prev < 6; prev++) {
                    if (dp[prev] == LLONG_MAX) continue;
                    
                    int prevC1 = validPairs[prev].first, prevC2 = validPairs[prev].second;
                    
                    // Check adjacency constraints
                    bool valid = true;
                    if (i == 1) {
                        // positions 0,1 and n-2,n-1 are adjacent
                        if (prevC1 == c1 || prevC2 == c2) valid = false;
                    } else {
                        // position i-1 is adjacent to position i
                        // position n-i is adjacent to position n-1-i
                        if (prevC2 == c1 || prevC1 == c2) valid = false;
                    }
                    
                    if (valid) {
                        newDp[k] = min(newDp[k], dp[prev] + currentCost);
                    }
                }
            }
            
            dp = newDp;
        }
        
        return *min_element(dp.begin(), dp.end());
    }
};

class Solution:
    def minCost(self, n: int, cost: List[List[int]]) -> int:
        valid_pairs = []
        for i in range(3):
            for j in range(3):
                if i != j:
                    valid_pairs.append((i, j))
        
        dp = [float('inf')] * 6
        
        # Initialize first pair
        for k in range(6):
            c1, c2 = valid_pairs[k]
            dp[k] = cost[0][c1] + cost[n-1][c2]
        
        for i in range(1, n//2):
            new_dp = [float('inf')] * 6
            
            for k in range(6):
                c1, c2 = valid_pairs[k]
                current_cost = cost[i][c1] + cost[n-1-i][c2]
                
                for prev in range(6):
                    if dp[prev] == float('inf'):
                        continue
                    
                    prev_c1, prev_c2 = valid_pairs[prev]
                    
                    # Check adjacency constraints
                    valid = True
                    if i == 1:
                        # positions 0,1 and n-2,n-1 are adjacent
                        if prev_c1 == c1 or prev_c2 == c2:
                            valid = False
                    else:
                        # position i-1 is adjacent to position i
                        # position n-i is adjacent to position n-1-i
                        if prev_c2 == c1 or prev_c1 == c2:
                            valid = False
                    
                    if valid:
                        new_dp[k] = min(new_dp[k], dp[prev] + current_cost)
            
            dp = new_dp
        
        return min(dp)

public class Solution {
    public long MinCost(int n, int[][] cost) {
        var validPairs = new List<(int, int)>();
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i != j) {
                    validPairs.Add((i, j));
                }
            }
        }
        
        long[] dp = new long[6];
        Array.Fill(dp, long.MaxValue);
        
        // Initialize first pair
        for (int k = 0; k < 6; k++) {
            var (c1, c2) = validPairs[k];
            dp[k] = cost[0][c1] + cost[n-1][c2];
        }
        
        for (int i = 1; i < n/2; i++) {
            long[] newDp = new long[6];
            Array.Fill(newDp, long.MaxValue);
            
            for (int k = 0; k < 6; k++) {
                var (c1, c2) = validPairs[k];
                long currentCost = cost[i][c1] + cost[n-1-i][c2];
                
                for (int prev = 0; prev < 6; prev++) {
                    if (dp[prev] == long.MaxValue) continue;
                    
                    var (prevC1, prevC2) = validPairs[prev];
                    
                    // Check adjacency constraints
                    bool valid = true;
                    if (i == 1) {
                        // positions 0,1 and n-2,n-1 are adjacent
                        if (prevC1 == c1 || prevC2 == c2) valid = false;
                    } else {
                        // position i-1 is adjacent to position i
                        // position n-i is adjacent to position n-1-i
                        if (prevC2 == c1 || prevC1 == c2) valid = false;
                    }
                    
                    if (valid) {
                        newDp[k] = Math.Min(newDp[k], dp[prev] + currentCost);
                    }
                }
            }
            
            dp = newDp;
        }
        
        return dp.Min();
    }
}

var minCost = function(n, cost) {
    const memo = new Map();
    
    function dp(pos, prevColor, colors) {
        if (pos === n) return 0;
        
        const key = `${pos},${prevColor},${colors.join(',')}`;
        if (memo.has(key)) return memo.get(key);
        
        let minCost = Infinity;
        
        for (let color = 0; color < 3; color++) {
            if (color === prevColor) continue;
            
            const mirrorPos = n - 1 - pos;
            if (pos < mirrorPos && colors[mirrorPos] === color) continue;
            if (pos > mirrorPos && colors[mirrorPos] !== color) continue;
            
            const newColors = [...colors];
            newColors[pos] = color;
            
            const currentCost = cost[pos][color] + dp(pos + 1, color, newColors);
            minCost = Math.min(minCost, currentCost);
        }
        
        memo.set(key, minCost);
        return minCost;
    }
    
    return dp(0, -1, new Array(n).fill(-1));
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n) - 需要处理 n/2 对房子，每对房子枚举常数个颜色组合
空间复杂度O(1) - 只使用了固定大小的 dp 数组存储状态

相关题目