1. 问题背景与核心挑战粉刷房子 II这道算法题表面上是关于房屋粉刷的颜色选择问题实际上是一个经典的动态规划(DP)练习题。题目描述为有n栋房子排成一排每栋房子可以用k种不同颜色中的一种进行粉刷且相邻两栋房子不能粉刷相同的颜色。给定一个n×k的成本矩阵求粉刷所有房子的最小总成本。这道题之所以被广泛讨论是因为它完美展现了动态规划的两个关键特性最优子结构当前最优解依赖于子问题的最优解重叠子问题相同子问题会被多次计算2. 基础解法分析2.1 暴力递归思路最直观的解法是使用递归穷举所有可能的粉刷方案def minCost(costs): n len(costs) k len(costs[0]) if n 0 else 0 def dfs(house, prev_color): if house n: return 0 min_cost float(inf) for color in range(k): if color ! prev_color: cost costs[house][color] dfs(house 1, color) min_cost min(min_cost, cost) return min_cost return dfs(0, -1)这种解法的时间复杂度是O(k^n)显然无法处理稍大规模的问题。2.2 记忆化递归优化通过添加备忘录来避免重复计算def minCost(costs): n len(costs) k len(costs[0]) if n 0 else 0 memo {} def dfs(house, prev_color): if (house, prev_color) in memo: return memo[(house, prev_color)] if house n: return 0 min_cost float(inf) for color in range(k): if color ! prev_color: cost costs[house][color] dfs(house 1, color) min_cost min(min_cost, cost) memo[(house, prev_color)] min_cost return min_cost return dfs(0, -1)时间复杂度优化到O(nk^2)因为共有n×k个状态每个状态需要O(k)时间计算。3. 动态规划优化技巧3.1 标准DP解法将递归转为迭代式DPdef minCost(costs): if not costs or not costs[0]: return 0 n, k len(costs), len(costs[0]) dp [[0]*k for _ in range(n)] # 初始化第一栋房子 for color in range(k): dp[0][color] costs[0][color] for house in range(1, n): for color in range(k): # 找出前一栋房子非color颜色的最小成本 min_prev float(inf) for prev_color in range(k): if prev_color ! color: min_prev min(min_prev, dp[house-1][prev_color]) dp[house][color] costs[house][color] min_prev return min(dp[-1])这种解法时间复杂度O(nk^2)空间复杂度O(nk)。3.2 空间优化技巧观察到当前状态只依赖于前一栋房子的状态可以优化空间def minCost(costs): if not costs or not costs[0]: return 0 n, k len(costs), len(costs[0]) prev_dp costs[0].copy() for house in range(1, n): curr_dp [0]*k for color in range(k): min_prev float(inf) for prev_color in range(k): if prev_color ! color: min_prev min(min_prev, prev_dp[prev_color]) curr_dp[color] costs[house][color] min_prev prev_dp curr_dp return min(prev_dp)空间复杂度降为O(k)。4. 进阶优化O(nk)解法4.1 优化思路关键观察点在计算每个颜色时我们只需要知道前一栋房子的最小成本和次小成本如果当前颜色不等于前一栋房子的最小成本对应的颜色直接使用最小成本否则使用次小成本4.2 实现代码def minCost(costs): if not costs or not costs[0]: return 0 n, k len(costs), len(costs[0]) prev_min1 prev_min2 0 prev_color1 -1 for house in range(n): curr_min1 curr_min2 float(inf) curr_color1 -1 for color in range(k): cost costs[house][color] if color prev_color1: cost prev_min2 else: cost prev_min1 if cost curr_min1: curr_min2 curr_min1 curr_min1 cost curr_color1 color elif cost curr_min2: curr_min2 cost prev_min1, prev_min2 curr_min1, curr_min2 prev_color1 curr_color1 return prev_min1这种解法将时间复杂度优化到O(nk)空间复杂度O(1)。5. 实际应用与变种5.1 实际应用场景这种DP优化技巧可以应用于资源分配问题如任务分配到不同机器路径规划问题如选择不同路线生产调度问题如选择不同生产线5.2 常见变种题目相邻房子颜色限制更复杂如前两栋不能同色成本计算方式变化如考虑颜色过渡的额外成本环形排列的房子首尾也视为相邻6. 调试与验证技巧6.1 测试用例设计设计测试用例时应考虑test_cases [ ([], 0), # 空输入 ([[1]], 1), # 单栋房子 ([[1,2],[1,2]], 2), # 两栋房子 ([[1,5,3],[2,9,4]], 5), # 典型情况 ([[17,2,17],[16,16,5],[14,3,19]], 10) # 复杂情况 ]6.2 调试技巧打印DP表格中间状态对每个house记录选择的颜色路径使用小规模数据手动验证7. 性能对比实测在不同规模下的性能对比单位毫秒数据规模暴力递归记忆化递归标准DP优化DPn10,k510000.50.20.1n100,k10超时520.5n1000,k20超时500200108. 经验总结DP问题先想清楚状态定义和转移方程空间优化时注意状态依赖关系寻找问题中的特殊性质可以进一步优化对于极值类问题记录前几个极值往往能简化计算这种优化思路不仅适用于粉刷房子问题也可以推广到其他类似的DP问题中。关键在于发现状态转移中的冗余计算并通过预处理或记录关键信息来消除这些冗余。