 时间 O(1) 空间的动态规划优化（LeetCode 题解）)
Paint House II 多色粉刷最小成本全解从记忆化搜索到 O(n·k) 时间 O(1) 空间的动态规划优化LeetCode 题解【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇文章基于当前仓库 articles/paint-house-ii.md 展开系统讲解经典动态规划问题Paint House IIK 色粉刷最小成本的五种解法从最直观的记忆化搜索开始逐步过渡到迭代 DP、O(k) 额外空间版本最终利用「最小值 次小值」追踪将时间复杂度压到 O(n·k)、空间复杂度压到 O(1)。读完本文你将掌握这道题从暴力到最优的完整思维链路理解「最小/次小值追踪」这一在排他性约束 DP 中极其通用的优化技巧并能将仓库中提供的 Python、Java、C、JavaScript、Go 等多语言实现直接用于刷题与面试复盘。问题背景与前置知识Paint House II 是 Paint House三色版本的直接推广现在有n栋房子排成一行每栋房子可以在k种颜色中选择一种涂刷costs[i][j]表示第i栋房子涂第j种颜色的花费。约束条件与三色版本完全一致——相邻两栋房子不能涂同一种颜色目标是求粉刷完全部n栋房子的最小总花费。仓库中 articles/paint-house.md 讲解了只有 3 种颜色的基础版本对应的三色实现可以参考 java/0256-paint-house.java固定 3 种颜色逐行用Math.min(dp[1], dp[2])这类「排除自身」的写法滚动更新。Paint House II 将颜色数从 3 扩展到任意的k此时再逐个枚举排除就变得昂贵这正是本文要解决的核心矛盾。开始解题前原文档要求读者具备以下前置能力二维动态规划2D DP用「房子下标 × 颜色」两个维度管理状态记忆化搜索Memoization缓存(house, color)子问题的结果避免重复计算最小/次小值追踪Minimum/Second-Minimum Tracking把每个格子的计算从 O(k) 降到 O(1)整体从 O(n·k²) 优化到 O(n·k)空间优化Space Optimization从 O(n·k) 逐步压缩到 O(k) 甚至 O(1)只保留必要的上一行数据。空输入是合法测试用例costs []时应直接返回0所有解法都显式处理了这一边界。解法一记忆化搜索自顶向下思路定义递归函数memoSolve(houseNumber, color)返回「当前房子涂成指定颜色后从它一直涂到最后一栋」的最小花费。递归过程中下一栋房子只能选择与当前颜色不同的任意颜色逐一递归取最小值。由于相同的(houseNumber, color)子问题会被反复求解用缓存避免重复计算。算法步骤定义递归函数memoSolve(houseNumber, color)返回从当前房子涂到结尾的最小成本基准情况若当前已是最后一栋房子houseNumber n - 1直接返回该房子涂此颜色的成本对下一栋房子遍历所有k种颜色跳过与当前颜色相同的选项递归求解剩余部分的最小成本将每个(houseNumber, color)的结果缓存起来对第0栋房子尝试所有颜色返回总成本的最小值。参考实现from functools import lru_cache class Solution: def minCostII(self, costs: List[List[int]]) - int: # Start by defining n and k to make the following code cleaner. n len(costs) if n 0: return 0 # No houses is a valid test case! k len(costs[0]) # If youre not familiar with lru_cache, look it up in the docs as its # essential to know about. lru_cache(maxsizeNone) def memo_solve(house_num, color): # Base case. if house_num n - 1: return costs[house_num][color] # Recursive case. cost math.inf for next_color in range(k): if next_color color: continue # Cant paint adjacent houses the same color! cost min(cost, memo_solve(house_num 1, next_color)) return costs[house_num][color] cost # Consider all options for painting house 0 and find the minimum. cost math.inf for color in range(k): cost min(cost, memo_solve(0, color)) return costclass Solution { private int n; private int k; private int[][] costs; private MapString, Integer memo; public int minCostII(int[][] costs) { if (costs.length 0) return 0; this.k costs[0].length; this.n costs.length; this.costs costs; this.memo new HashMap(); int minCost Integer.MAX_VALUE; for (int color 0; color k; color) { minCost Math.min(minCost, memoSolve(0, color)); } return minCost; } private int memoSolve(int houseNumber, int color) { // Base case: There are no more houses after this one. if (houseNumber n - 1) { return costs[houseNumber][color]; } // Memoization lookup case: Have we already solved this subproblem? if (memo.containsKey(getKey(houseNumber, color))) { return memo.get(getKey(houseNumber, color)); } // Recursive case: Determine the minimum cost for the remainder. int minRemainingCost Integer.MAX_VALUE; for (int nextColor 0; nextColor k; nextColor) { if (color nextColor) continue; int currentRemainingCost memoSolve(houseNumber 1, nextColor); minRemainingCost Math.min(currentRemainingCost, minRemainingCost); } int totalCost costs[houseNumber][color] minRemainingCost; memo.put(getKey(houseNumber, color), totalCost); return totalCost; } // Convert a house number and color into a simple string key for the memo. private String getKey(int n, int color) { return String.valueOf(n) String.valueOf(color); } }其余语言C、JavaScript、C#、Go、Kotlin、Swift、Rust的完整实现均收录于仓库原文档的选项卡中。其中 C 用unordered_mapstring, int、Go 用map[string]int、Rust 用HashMap(usize, usize), i32作为缓存缓存键统一编码为「房子下标 颜色」。复杂度分析时间复杂度$O(n \cdot k^2)$ —— 每个(house, color)状态都要遍历一遍其余颜色空间复杂度$O(n \cdot k)$ —— 缓存了全部子问题结果不含递归栈本身。其中 $n$ 为房子数量$k$ 为可用颜色数。解法二迭代动态规划原地修改输入思路记忆化搜索可以改写为自底向上的迭代版本逐栋房子累积「涂到当前房子为止」的最小成本。对每一栋房子、每一种颜色我们需要的是上一行中所有不同颜色的最小值。最直接的写法就是遍历上一行的全部k个颜色求最小于是每个格子需要 O(k) 工作量整体 O(n·k²)。算法步骤从下标1到n-1依次处理房子第0栋房子的成本就是给定的涂刷成本对每栋房子的每种颜色在上一行所有不同颜色中找出最小成本将该最小值累加到当前涂刷成本上并原地更新costs数组所有房子处理完毕后返回最后一行中的最小值。参考实现class Solution: def minCostII(self, costs: List[List[int]]) - int: n len(costs) if n 0: return 0 k len(costs[0]) for house in range(1, n): for color in range(k): best math.inf for previous_color in range(k): if color previous_color: continue best min(best, costs[house - 1][previous_color]) costs[house][color] best return min(costs[-1])class Solution { public int minCostII(int[][] costs) { if (costs.length 0) return 0; int k costs[0].length; int n costs.length; for (int house 1; house n; house) { for (int color 0; color k; color) { int min Integer.MAX_VALUE; for (int previousColor 0; previousColor k; previousColor) { if (color previousColor) continue; min Math.min(min, costs[house - 1][previousColor]); } costs[house][color] min; } } // Find the minimum in the last row. int min Integer.MAX_VALUE; for (int c : costs[n - 1]) { min Math.min(min, c); } return min; } }复杂度分析时间复杂度$O(n \cdot k^2)$空间复杂度$O(1)$原地修改输入若复制输入则为 $O(n \cdot k)$。其中 $n$ 为房子数量$k$ 为可用颜色数。注意本解法会修改传入的costs数组——这在原文档的「常见陷阱」一节中被单独指出如果调用方依赖原始数据应当改用不修改输入的版本。解法三动态规划 O(k) 额外空间不修改输入思路解法二修改了输入数组。若希望保留原始数据可以维护一个长度为k的辅助数组previousRow记录上一行的累计成本。逻辑完全一致只是不再原地写回输入而是每处理完一栋房子就交换previousRow与新建的currentRow。算法步骤将costs第一行复制到previousRow对后续每栋房子新建一个currentRow数组对每种颜色在previousRow中找出排除同色下标后的最小值加上当前涂刷成本处理完一栋房子后令previousRow currentRow返回最终previousRow中的最小值。参考实现def minCostII(self, costs: List[List[int]]) - int: n len(costs) if n 0: return 0 k len(costs[0]) previous_row costs[0] for house in range(1, n): current_row [0] * k for color in range(k): best math.inf for previous_color in range(k): if color previous_color: continue best min(best, previous_row[previous_color]) current_row[color] costs[house][color] best previous_row current_row return min(previous_row)class Solution { public int minCostII(int[][] costs) { if (costs.length 0) return 0; int k costs[0].length; int n costs.length; int[] previousRow costs[0]; for (int house 1; house n; house) { int[] currentRow new int[k]; for (int color 0; color k; color) { int min Integer.MAX_VALUE; for (int previousColor 0; previousColor k; previousColor) { if (color previousColor) continue; min Math.min(min, previousRow[previousColor]); } currentRow[color] costs[house][color] min; } previousRow currentRow; } // Find the minimum in the last row. int min Integer.MAX_VALUE; for (int c : previousRow) { min Math.min(min, c); } return min; } }复杂度分析时间复杂度$O(n \cdot k^2)$空间复杂度$O(k)$只保留两行长度为k的数组。其中 $n$ 为房子数量$k$ 为可用颜色数。相比解法二本解法以 $O(k)$ 空间换取了输入数组的不可变性。解法四时间优化到 O(n·k)最小/次小值追踪思路前三种解法的时间瓶颈都在于为当前行的每种颜色都要在上一行里扫描一遍求「排除同色后的最小值」每栋房子 O(k²)。仔细观察可以发现一个关键事实对上一行来说除了「上一行最小成本对应的那个颜色」之外其余所有颜色需要的都只是上一行的全局最小值唯一的例外是当前颜色恰好等于上一行最小颜色时需要退而求其次使用上一行的次小值。因此只要预先算出上一行的最小值、次小值以及最小值对应的颜色下标当前行的每个格子就能在 O(1) 时间内更新整栋房子的工作量从 O(k²) 降到 O(k)整体复杂度降为 O(n·k)。算法步骤从第1栋房子开始先在上一行中找到最小成本与次小成本各自对应的颜色下标更新当前行每种颜色时若当前颜色恰是上一行的最小颜色则累加次小值否则累加最小值重复处理直到所有房子完成返回最后一行的最小值。参考实现class Solution: def minCostII(self, costs: List[List[int]]) - int: n len(costs) if n 0: return 0 k len(costs[0]) for house in range(1, n): # Find the colors with the minimum and second to minimum # in the previous row. min_color second_min_color None for color in range(k): cost costs[house - 1][color] if min_color is None or cost costs[house - 1][min_color]: second_min_color min_color min_color color elif second_min_color is None or cost costs[house - 1][second_min_color]: second_min_color color # And now update the costs for the current row. for color in range(k): if color min_color: costs[house][color] costs[house - 1][second_min_color] else: costs[house][color] costs[house - 1][min_color] # The answer will now be the minimum of the last row. return min(costs[-1])class Solution { public int minCostII(int[][] costs) { if (costs.length 0) return 0; int k costs[0].length; int n costs.length; for (int house 1; house n; house) { // Find the minimum and second minimum color in the PREVIOUS row. int minColor -1; int secondMinColor -1; for (int color 0; color k; color) { int cost costs[house - 1][color]; if (minColor -1 || cost costs[house - 1][minColor]) { secondMinColor minColor; minColor color; } else if (secondMinColor -1 || cost costs[house - 1][secondMinColor]) { secondMinColor color; } } // And now calculate the new costs for the current row. for (int color 0; color k; color) { if (color minColor) { costs[house][color] costs[house - 1][secondMinColor]; } else { costs[house][color] costs[house - 1][minColor]; } } } // Find the minimum in the last row. int min Integer.MAX_VALUE; for (int c : costs[n - 1]) { min Math.min(min, c); } return min; } }求最小/次小值下标的双指针逻辑值得单独说明扫描上一行时若当前成本比已知最小值还小就把旧最小值降级为次小值、当前颜色升级为最小值否则若比已知次小值还小则仅更新次小值。这一模式同样适用于 Rust 实现中min_color as usize的索引转换。复杂度分析时间复杂度$O(n \cdot k)$ —— 每栋房子一次 O(k) 扫描找最小/次小 一次 O(k) 更新空间复杂度$O(1)$原地修改输入。其中 $n$ 为房子数量$k$ 为可用颜色数。解法五时间与空间双重优化仅保留三个标量思路解法四虽然时间最优但仍保留整行数据。进一步观察可以发现处理下一行时上一行的完整数据里只有三个信息是必要的——最小成本、次小成本、以及取得最小值的颜色下标。于是我们彻底丢掉数组只用三个标量滚动推进在保持 O(n·k) 时间的同时把空间压到 O(1)且完全不需要修改输入数组。算法步骤初始化从第一行中找到最小值、次小值以及最小值对应的颜色下标对后续每栋房子遍历所有颜色若当前颜色等于上一行最小颜色则成本为当前涂刷成本 上一行次小值否则成本为当前涂刷成本 上一行最小值在遍历每种颜色的同时动态维护本行的新最小值、新次小值、新最小颜色下标全部处理完后最后保留的最小值即为答案。参考实现class Solution: def minCostII(self, costs: List[List[int]]) - int: n len(costs) if n 0: return 0 # This is a valid case. k len(costs[0]) # Firstly, we need to determine the 2 lowest costs of # the first row. We also need to remember the color of # the lowest. prev_min_cost prev_second_min_cost prev_min_color None for color, cost in enumerate(costs[0]): if prev_min_cost is None or cost prev_min_cost: prev_second_min_cost prev_min_cost prev_min_color color prev_min_cost cost elif prev_second_min_cost is None or cost prev_second_min_cost: prev_second_min_cost cost # And now, we need to work our way down, keeping track of the minimums. for house in range(1, n): min_cost second_min_cost min_color None for color in range(k): # Determime cost for this cell (without writing it into input array.) cost costs[house][color] if color prev_min_color: cost prev_second_min_cost else: cost prev_min_cost # And work out whether or not it is a current minimum. if min_cost is None or cost min_cost: second_min_cost min_cost min_color color min_cost cost elif second_min_cost is None or cost second_min_cost: second_min_cost cost # Transfer currents to be prevs. prev_min_cost min_cost prev_min_color min_color prev_second_min_cost second_min_cost return prev_min_costclass Solution { public int minCostII(int[][] costs) { if (costs.length 0) return 0; int k costs[0].length; int n costs.length; /* Firstly, we need to determine the 2 lowest costs of * the first row. We also need to remember the color of * the lowest. */ int prevMin -1; int prevSecondMin -1; int prevMinColor -1; for (int color 0; color k; color) { int cost costs[0][color]; if (prevMin -1 || cost prevMin) { prevSecondMin prevMin; prevMinColor color; prevMin cost; } else if (prevSecondMin -1 || cost prevSecondMin) { prevSecondMin cost; } } // And now, we need to work our way down, keeping track of the minimums. for (int house 1; house n; house) { int min -1; int secondMin -1; int minColor -1; for (int color 0; color k; color) { // Determine the cost for this cell (without writing it in). int cost costs[house][color]; if (color prevMinColor) { cost prevSecondMin; } else { cost prevMin; } // Determine whether or not this current cost is also a minimum. if (min -1 || cost min) { secondMin min; minColor color; min cost; } else if (secondMin -1 || cost secondMin) { secondMin cost; } } // Transfer current mins to be previous mins. prevMin min; prevSecondMin secondMin; prevMinColor minColor; } return prevMin; } }复杂度分析时间复杂度$O(n \cdot k)$空间复杂度$O(1)$仅三个标量。其中 $n$ 为房子数量$k$ 为可用颜色数。这是空间占用最小的版本且无需修改输入兼顾了解法三的「输入不可变」与解法四的时间最优。五种解法复杂度对照解法时间空间是否修改输入备注1. 记忆化搜索$O(n \cdot k^2)$$O(n \cdot k)$否自顶向下思路最直观2. 迭代 DP原地$O(n \cdot k^2)$$O(1)$是依赖原地写回3. 迭代 DP O(k) 空间$O(n \cdot k^2)$$O(k)$否保留输入的折中方案4. 时间优化最小/次小追踪$O(n \cdot k)$$O(1)$是时间最优仍需整行数据5. 时间与空间双重优化$O(n \cdot k)$$O(1)$否时间空间同时最优其中 $n$ 为房子数量$k$ 为可用颜色数。面试中推荐优先掌握解法 2 与解法 4 的思维解法 5 则用于展示对「排他性约束」状态的极致压缩能力。常见陷阱1. 每栋房子使用 O(k²) 时间而不做优化最朴素的写法是为当前行每种颜色都扫描上一行全部k个颜色求最小值整体退化为 O(n·k²)。当k很大时会超时。核心洞察是上一行只需要维护最小值与次小值两个信息即可把每栋房子的工作量降为 O(k)。2. 没有处理 k 等于 1 的情况当只有一种颜色可用时只要房子数量大于 1 就不可能满足「相邻不同色」的约束。部分实现假设k 2在k 1 n 1时可能崩溃或返回错误结果。务必显式检查该情况并妥善处理。3. 忘记记录取得最小值的颜色下标做最小/次小值优化时必须同时记住哪个颜色取得了最小值。否则处理下一行时无法判断当前颜色是否命中上一行的最小颜色也就无法决定该用最小值还是次小值。4. 意外修改了输入数组解法二、解法四为省空间在costs上原地更新。如果调用方期望原始数据保持不变这可能引发问题。应对方式要么在文档/注释中明确该行为要么拷贝输入要么直接使用解法五这类只追踪必要标量、不写回输入的做法。5. 房子下标越界Off-by-OneDP 从下标1处理到n-1以第0栋房子作为基准。混淆 0 基与 1 基循环、或错误引用costs[house - 1]与costs[house]会导致读取到错误的花费甚至数组越界。仓库中的多语言实现与延伸阅读原文档 articles/paint-house-ii.md 为上述五种解法均提供了Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust九种语言的完整实现以选项卡形式组织可以直接对照学习各语言在记忆化缓存键、min聚合、数组拷贝如 JavaScript 的[...costs[0]]、C# 的Clone()、Go 的copy等方面的惯用写法。与之配套的仓库资源还包括Paint House三色版本题解掌握 3 种颜色固定版本的递归与 DP 写法有助于理解本题的推广逻辑Paint House 的 Java 实现固定三色时用Math.min(dp[1], dp[2])等「两两排除」的方式滚动更新是本题 O(n·k) 优化思路的雏形仓库 README了解本仓库的定位NeetCode 题解合集、多语言覆盖文章编写指南了解仓库内题解文章的统一结构要求至少一种解法贴近视频、附带时间与空间复杂度、尽量覆盖全部相关解法。建议的练习路径先用解法一理解递归结构与状态定义再手写解法二体会自底向上转移最后推导出解法四的「最小/次小值」技巧并用解法五压缩空间——这条路径能把一道中等偏难的 DP 题转化为一套可复用的「排他性约束 DP」方法论。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
Paint House II 多色粉刷最小成本全解：从记忆化搜索到 O(n·k) 时间 O(1) 空间的动态规划优化（LeetCode 题解）
Paint House II 多色粉刷最小成本全解从记忆化搜索到 O(n·k) 时间 O(1) 空间的动态规划优化LeetCode 题解【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇文章基于当前仓库 articles/paint-house-ii.md 展开系统讲解经典动态规划问题Paint House IIK 色粉刷最小成本的五种解法从最直观的记忆化搜索开始逐步过渡到迭代 DP、O(k) 额外空间版本最终利用「最小值 次小值」追踪将时间复杂度压到 O(n·k)、空间复杂度压到 O(1)。读完本文你将掌握这道题从暴力到最优的完整思维链路理解「最小/次小值追踪」这一在排他性约束 DP 中极其通用的优化技巧并能将仓库中提供的 Python、Java、C、JavaScript、Go 等多语言实现直接用于刷题与面试复盘。问题背景与前置知识Paint House II 是 Paint House三色版本的直接推广现在有n栋房子排成一行每栋房子可以在k种颜色中选择一种涂刷costs[i][j]表示第i栋房子涂第j种颜色的花费。约束条件与三色版本完全一致——相邻两栋房子不能涂同一种颜色目标是求粉刷完全部n栋房子的最小总花费。仓库中 articles/paint-house.md 讲解了只有 3 种颜色的基础版本对应的三色实现可以参考 java/0256-paint-house.java固定 3 种颜色逐行用Math.min(dp[1], dp[2])这类「排除自身」的写法滚动更新。Paint House II 将颜色数从 3 扩展到任意的k此时再逐个枚举排除就变得昂贵这正是本文要解决的核心矛盾。开始解题前原文档要求读者具备以下前置能力二维动态规划2D DP用「房子下标 × 颜色」两个维度管理状态记忆化搜索Memoization缓存(house, color)子问题的结果避免重复计算最小/次小值追踪Minimum/Second-Minimum Tracking把每个格子的计算从 O(k) 降到 O(1)整体从 O(n·k²) 优化到 O(n·k)空间优化Space Optimization从 O(n·k) 逐步压缩到 O(k) 甚至 O(1)只保留必要的上一行数据。空输入是合法测试用例costs []时应直接返回0所有解法都显式处理了这一边界。解法一记忆化搜索自顶向下思路定义递归函数memoSolve(houseNumber, color)返回「当前房子涂成指定颜色后从它一直涂到最后一栋」的最小花费。递归过程中下一栋房子只能选择与当前颜色不同的任意颜色逐一递归取最小值。由于相同的(houseNumber, color)子问题会被反复求解用缓存避免重复计算。算法步骤定义递归函数memoSolve(houseNumber, color)返回从当前房子涂到结尾的最小成本基准情况若当前已是最后一栋房子houseNumber n - 1直接返回该房子涂此颜色的成本对下一栋房子遍历所有k种颜色跳过与当前颜色相同的选项递归求解剩余部分的最小成本将每个(houseNumber, color)的结果缓存起来对第0栋房子尝试所有颜色返回总成本的最小值。参考实现from functools import lru_cache class Solution: def minCostII(self, costs: List[List[int]]) - int: # Start by defining n and k to make the following code cleaner. n len(costs) if n 0: return 0 # No houses is a valid test case! k len(costs[0]) # If youre not familiar with lru_cache, look it up in the docs as its # essential to know about. lru_cache(maxsizeNone) def memo_solve(house_num, color): # Base case. if house_num n - 1: return costs[house_num][color] # Recursive case. cost math.inf for next_color in range(k): if next_color color: continue # Cant paint adjacent houses the same color! cost min(cost, memo_solve(house_num 1, next_color)) return costs[house_num][color] cost # Consider all options for painting house 0 and find the minimum. cost math.inf for color in range(k): cost min(cost, memo_solve(0, color)) return costclass Solution { private int n; private int k; private int[][] costs; private MapString, Integer memo; public int minCostII(int[][] costs) { if (costs.length 0) return 0; this.k costs[0].length; this.n costs.length; this.costs costs; this.memo new HashMap(); int minCost Integer.MAX_VALUE; for (int color 0; color k; color) { minCost Math.min(minCost, memoSolve(0, color)); } return minCost; } private int memoSolve(int houseNumber, int color) { // Base case: There are no more houses after this one. if (houseNumber n - 1) { return costs[houseNumber][color]; } // Memoization lookup case: Have we already solved this subproblem? if (memo.containsKey(getKey(houseNumber, color))) { return memo.get(getKey(houseNumber, color)); } // Recursive case: Determine the minimum cost for the remainder. int minRemainingCost Integer.MAX_VALUE; for (int nextColor 0; nextColor k; nextColor) { if (color nextColor) continue; int currentRemainingCost memoSolve(houseNumber 1, nextColor); minRemainingCost Math.min(currentRemainingCost, minRemainingCost); } int totalCost costs[houseNumber][color] minRemainingCost; memo.put(getKey(houseNumber, color), totalCost); return totalCost; } // Convert a house number and color into a simple string key for the memo. private String getKey(int n, int color) { return String.valueOf(n) String.valueOf(color); } }其余语言C、JavaScript、C#、Go、Kotlin、Swift、Rust的完整实现均收录于仓库原文档的选项卡中。其中 C 用unordered_mapstring, int、Go 用map[string]int、Rust 用HashMap(usize, usize), i32作为缓存缓存键统一编码为「房子下标 颜色」。复杂度分析时间复杂度$O(n \cdot k^2)$ —— 每个(house, color)状态都要遍历一遍其余颜色空间复杂度$O(n \cdot k)$ —— 缓存了全部子问题结果不含递归栈本身。其中 $n$ 为房子数量$k$ 为可用颜色数。解法二迭代动态规划原地修改输入思路记忆化搜索可以改写为自底向上的迭代版本逐栋房子累积「涂到当前房子为止」的最小成本。对每一栋房子、每一种颜色我们需要的是上一行中所有不同颜色的最小值。最直接的写法就是遍历上一行的全部k个颜色求最小于是每个格子需要 O(k) 工作量整体 O(n·k²)。算法步骤从下标1到n-1依次处理房子第0栋房子的成本就是给定的涂刷成本对每栋房子的每种颜色在上一行所有不同颜色中找出最小成本将该最小值累加到当前涂刷成本上并原地更新costs数组所有房子处理完毕后返回最后一行中的最小值。参考实现class Solution: def minCostII(self, costs: List[List[int]]) - int: n len(costs) if n 0: return 0 k len(costs[0]) for house in range(1, n): for color in range(k): best math.inf for previous_color in range(k): if color previous_color: continue best min(best, costs[house - 1][previous_color]) costs[house][color] best return min(costs[-1])class Solution { public int minCostII(int[][] costs) { if (costs.length 0) return 0; int k costs[0].length; int n costs.length; for (int house 1; house n; house) { for (int color 0; color k; color) { int min Integer.MAX_VALUE; for (int previousColor 0; previousColor k; previousColor) { if (color previousColor) continue; min Math.min(min, costs[house - 1][previousColor]); } costs[house][color] min; } } // Find the minimum in the last row. int min Integer.MAX_VALUE; for (int c : costs[n - 1]) { min Math.min(min, c); } return min; } }复杂度分析时间复杂度$O(n \cdot k^2)$空间复杂度$O(1)$原地修改输入若复制输入则为 $O(n \cdot k)$。其中 $n$ 为房子数量$k$ 为可用颜色数。注意本解法会修改传入的costs数组——这在原文档的「常见陷阱」一节中被单独指出如果调用方依赖原始数据应当改用不修改输入的版本。解法三动态规划 O(k) 额外空间不修改输入思路解法二修改了输入数组。若希望保留原始数据可以维护一个长度为k的辅助数组previousRow记录上一行的累计成本。逻辑完全一致只是不再原地写回输入而是每处理完一栋房子就交换previousRow与新建的currentRow。算法步骤将costs第一行复制到previousRow对后续每栋房子新建一个currentRow数组对每种颜色在previousRow中找出排除同色下标后的最小值加上当前涂刷成本处理完一栋房子后令previousRow currentRow返回最终previousRow中的最小值。参考实现def minCostII(self, costs: List[List[int]]) - int: n len(costs) if n 0: return 0 k len(costs[0]) previous_row costs[0] for house in range(1, n): current_row [0] * k for color in range(k): best math.inf for previous_color in range(k): if color previous_color: continue best min(best, previous_row[previous_color]) current_row[color] costs[house][color] best previous_row current_row return min(previous_row)class Solution { public int minCostII(int[][] costs) { if (costs.length 0) return 0; int k costs[0].length; int n costs.length; int[] previousRow costs[0]; for (int house 1; house n; house) { int[] currentRow new int[k]; for (int color 0; color k; color) { int min Integer.MAX_VALUE; for (int previousColor 0; previousColor k; previousColor) { if (color previousColor) continue; min Math.min(min, previousRow[previousColor]); } currentRow[color] costs[house][color] min; } previousRow currentRow; } // Find the minimum in the last row. int min Integer.MAX_VALUE; for (int c : previousRow) { min Math.min(min, c); } return min; } }复杂度分析时间复杂度$O(n \cdot k^2)$空间复杂度$O(k)$只保留两行长度为k的数组。其中 $n$ 为房子数量$k$ 为可用颜色数。相比解法二本解法以 $O(k)$ 空间换取了输入数组的不可变性。解法四时间优化到 O(n·k)最小/次小值追踪思路前三种解法的时间瓶颈都在于为当前行的每种颜色都要在上一行里扫描一遍求「排除同色后的最小值」每栋房子 O(k²)。仔细观察可以发现一个关键事实对上一行来说除了「上一行最小成本对应的那个颜色」之外其余所有颜色需要的都只是上一行的全局最小值唯一的例外是当前颜色恰好等于上一行最小颜色时需要退而求其次使用上一行的次小值。因此只要预先算出上一行的最小值、次小值以及最小值对应的颜色下标当前行的每个格子就能在 O(1) 时间内更新整栋房子的工作量从 O(k²) 降到 O(k)整体复杂度降为 O(n·k)。算法步骤从第1栋房子开始先在上一行中找到最小成本与次小成本各自对应的颜色下标更新当前行每种颜色时若当前颜色恰是上一行的最小颜色则累加次小值否则累加最小值重复处理直到所有房子完成返回最后一行的最小值。参考实现class Solution: def minCostII(self, costs: List[List[int]]) - int: n len(costs) if n 0: return 0 k len(costs[0]) for house in range(1, n): # Find the colors with the minimum and second to minimum # in the previous row. min_color second_min_color None for color in range(k): cost costs[house - 1][color] if min_color is None or cost costs[house - 1][min_color]: second_min_color min_color min_color color elif second_min_color is None or cost costs[house - 1][second_min_color]: second_min_color color # And now update the costs for the current row. for color in range(k): if color min_color: costs[house][color] costs[house - 1][second_min_color] else: costs[house][color] costs[house - 1][min_color] # The answer will now be the minimum of the last row. return min(costs[-1])class Solution { public int minCostII(int[][] costs) { if (costs.length 0) return 0; int k costs[0].length; int n costs.length; for (int house 1; house n; house) { // Find the minimum and second minimum color in the PREVIOUS row. int minColor -1; int secondMinColor -1; for (int color 0; color k; color) { int cost costs[house - 1][color]; if (minColor -1 || cost costs[house - 1][minColor]) { secondMinColor minColor; minColor color; } else if (secondMinColor -1 || cost costs[house - 1][secondMinColor]) { secondMinColor color; } } // And now calculate the new costs for the current row. for (int color 0; color k; color) { if (color minColor) { costs[house][color] costs[house - 1][secondMinColor]; } else { costs[house][color] costs[house - 1][minColor]; } } } // Find the minimum in the last row. int min Integer.MAX_VALUE; for (int c : costs[n - 1]) { min Math.min(min, c); } return min; } }求最小/次小值下标的双指针逻辑值得单独说明扫描上一行时若当前成本比已知最小值还小就把旧最小值降级为次小值、当前颜色升级为最小值否则若比已知次小值还小则仅更新次小值。这一模式同样适用于 Rust 实现中min_color as usize的索引转换。复杂度分析时间复杂度$O(n \cdot k)$ —— 每栋房子一次 O(k) 扫描找最小/次小 一次 O(k) 更新空间复杂度$O(1)$原地修改输入。其中 $n$ 为房子数量$k$ 为可用颜色数。解法五时间与空间双重优化仅保留三个标量思路解法四虽然时间最优但仍保留整行数据。进一步观察可以发现处理下一行时上一行的完整数据里只有三个信息是必要的——最小成本、次小成本、以及取得最小值的颜色下标。于是我们彻底丢掉数组只用三个标量滚动推进在保持 O(n·k) 时间的同时把空间压到 O(1)且完全不需要修改输入数组。算法步骤初始化从第一行中找到最小值、次小值以及最小值对应的颜色下标对后续每栋房子遍历所有颜色若当前颜色等于上一行最小颜色则成本为当前涂刷成本 上一行次小值否则成本为当前涂刷成本 上一行最小值在遍历每种颜色的同时动态维护本行的新最小值、新次小值、新最小颜色下标全部处理完后最后保留的最小值即为答案。参考实现class Solution: def minCostII(self, costs: List[List[int]]) - int: n len(costs) if n 0: return 0 # This is a valid case. k len(costs[0]) # Firstly, we need to determine the 2 lowest costs of # the first row. We also need to remember the color of # the lowest. prev_min_cost prev_second_min_cost prev_min_color None for color, cost in enumerate(costs[0]): if prev_min_cost is None or cost prev_min_cost: prev_second_min_cost prev_min_cost prev_min_color color prev_min_cost cost elif prev_second_min_cost is None or cost prev_second_min_cost: prev_second_min_cost cost # And now, we need to work our way down, keeping track of the minimums. for house in range(1, n): min_cost second_min_cost min_color None for color in range(k): # Determime cost for this cell (without writing it into input array.) cost costs[house][color] if color prev_min_color: cost prev_second_min_cost else: cost prev_min_cost # And work out whether or not it is a current minimum. if min_cost is None or cost min_cost: second_min_cost min_cost min_color color min_cost cost elif second_min_cost is None or cost second_min_cost: second_min_cost cost # Transfer currents to be prevs. prev_min_cost min_cost prev_min_color min_color prev_second_min_cost second_min_cost return prev_min_costclass Solution { public int minCostII(int[][] costs) { if (costs.length 0) return 0; int k costs[0].length; int n costs.length; /* Firstly, we need to determine the 2 lowest costs of * the first row. We also need to remember the color of * the lowest. */ int prevMin -1; int prevSecondMin -1; int prevMinColor -1; for (int color 0; color k; color) { int cost costs[0][color]; if (prevMin -1 || cost prevMin) { prevSecondMin prevMin; prevMinColor color; prevMin cost; } else if (prevSecondMin -1 || cost prevSecondMin) { prevSecondMin cost; } } // And now, we need to work our way down, keeping track of the minimums. for (int house 1; house n; house) { int min -1; int secondMin -1; int minColor -1; for (int color 0; color k; color) { // Determine the cost for this cell (without writing it in). int cost costs[house][color]; if (color prevMinColor) { cost prevSecondMin; } else { cost prevMin; } // Determine whether or not this current cost is also a minimum. if (min -1 || cost min) { secondMin min; minColor color; min cost; } else if (secondMin -1 || cost secondMin) { secondMin cost; } } // Transfer current mins to be previous mins. prevMin min; prevSecondMin secondMin; prevMinColor minColor; } return prevMin; } }复杂度分析时间复杂度$O(n \cdot k)$空间复杂度$O(1)$仅三个标量。其中 $n$ 为房子数量$k$ 为可用颜色数。这是空间占用最小的版本且无需修改输入兼顾了解法三的「输入不可变」与解法四的时间最优。五种解法复杂度对照解法时间空间是否修改输入备注1. 记忆化搜索$O(n \cdot k^2)$$O(n \cdot k)$否自顶向下思路最直观2. 迭代 DP原地$O(n \cdot k^2)$$O(1)$是依赖原地写回3. 迭代 DP O(k) 空间$O(n \cdot k^2)$$O(k)$否保留输入的折中方案4. 时间优化最小/次小追踪$O(n \cdot k)$$O(1)$是时间最优仍需整行数据5. 时间与空间双重优化$O(n \cdot k)$$O(1)$否时间空间同时最优其中 $n$ 为房子数量$k$ 为可用颜色数。面试中推荐优先掌握解法 2 与解法 4 的思维解法 5 则用于展示对「排他性约束」状态的极致压缩能力。常见陷阱1. 每栋房子使用 O(k²) 时间而不做优化最朴素的写法是为当前行每种颜色都扫描上一行全部k个颜色求最小值整体退化为 O(n·k²)。当k很大时会超时。核心洞察是上一行只需要维护最小值与次小值两个信息即可把每栋房子的工作量降为 O(k)。2. 没有处理 k 等于 1 的情况当只有一种颜色可用时只要房子数量大于 1 就不可能满足「相邻不同色」的约束。部分实现假设k 2在k 1 n 1时可能崩溃或返回错误结果。务必显式检查该情况并妥善处理。3. 忘记记录取得最小值的颜色下标做最小/次小值优化时必须同时记住哪个颜色取得了最小值。否则处理下一行时无法判断当前颜色是否命中上一行的最小颜色也就无法决定该用最小值还是次小值。4. 意外修改了输入数组解法二、解法四为省空间在costs上原地更新。如果调用方期望原始数据保持不变这可能引发问题。应对方式要么在文档/注释中明确该行为要么拷贝输入要么直接使用解法五这类只追踪必要标量、不写回输入的做法。5. 房子下标越界Off-by-OneDP 从下标1处理到n-1以第0栋房子作为基准。混淆 0 基与 1 基循环、或错误引用costs[house - 1]与costs[house]会导致读取到错误的花费甚至数组越界。仓库中的多语言实现与延伸阅读原文档 articles/paint-house-ii.md 为上述五种解法均提供了Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust九种语言的完整实现以选项卡形式组织可以直接对照学习各语言在记忆化缓存键、min聚合、数组拷贝如 JavaScript 的[...costs[0]]、C# 的Clone()、Go 的copy等方面的惯用写法。与之配套的仓库资源还包括Paint House三色版本题解掌握 3 种颜色固定版本的递归与 DP 写法有助于理解本题的推广逻辑Paint House 的 Java 实现固定三色时用Math.min(dp[1], dp[2])等「两两排除」的方式滚动更新是本题 O(n·k) 优化思路的雏形仓库 README了解本仓库的定位NeetCode 题解合集、多语言覆盖文章编写指南了解仓库内题解文章的统一结构要求至少一种解法贴近视频、附带时间与空间复杂度、尽量覆盖全部相关解法。建议的练习路径先用解法一理解递归结构与状态定义再手写解法二体会自底向上转移最后推导出解法四的「最小/次小值」技巧并用解法五压缩空间——这条路径能把一道中等偏难的 DP 题转化为一套可复用的「排他性约束 DP」方法论。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
