线性动态规划：粉刷房子 II（Paint House II） 题目描述 假设有n幢房子排成一排，每幢房子可以用k种颜色中的一种进行粉刷（k可能很大）。粉刷第i幢房子使用第j种颜色的成本是costs[ i][ j ]。要求是相邻两幢房子不能粉刷相同的颜色。你需要找出粉刷所有房子的最小总成本。 示例 输入：costs = [ [ 1,5,3],[ 2,9,4] ] 输出：5 解释：第一幢房子用颜色0（成本1），第二幢房子用颜色2（成本4），总成本=1+4=5。 解题过程 状态定义 定义dp[ i][ j ]表示粉刷前i幢房子，并且第i幢房子使用颜色j的最小总成本。 基础情况 当只有第一幢房子时（i=0），粉刷成本就是对应的颜色成本： dp[ 0][ j] = costs[ 0][ j ] （对于所有颜色j） 状态转移方程 对于第i幢房子（i≥1），如果它使用颜色j，那么第i-1幢房子不能使用颜色j，所以： dp[ i][ j] = min{ dp[ i-1][ c] | c ≠ j } + costs[ i][ j ] 即，当前房子的成本加上前一个房子使用 非j颜色 的最小成本。 直接实现的复杂度问题 如果直接按照上述方程实现，对于每个房子i和颜色j，都需要遍历k种颜色（除j外）来找最小值，总时间复杂度为O(n k²)。当k很大时（比如k=1000），n k²可能达到10^9，效率较低。 优化思路 实际上，对于每个位置i，我们只需要知道前一个位置的所有颜色的最小成本和次小成本，以及最小成本对应的颜色索引： 如果当前颜色j与前一个位置最小成本的颜色不同，那么前一个位置的最小成本可以直接使用。 如果当前颜色j恰好是前一个位置最小成本的颜色，那么我们就使用次小成本（因为相邻房子不能同色）。 这样，对于每个位置i，我们只需要： 先遍历一次所有颜色，计算前一个位置dp[ i-1 ]的最小值min1、次小值min2，以及最小值对应的颜色idx。 再遍历当前颜色j： 如果j ≠ idx，则dp[ i][ j] = min1 + costs[ i][ j ] 如果j == idx，则dp[ i][ j] = min2 + costs[ i][ j ] 这样就把内层循环的O(k)降为O(1)，总复杂度优化到O(n* k)。 优化后的状态转移步骤 初始化：dp[ 0][ j] = costs[ 0][ j ]（j从0到k-1） 对于i从1到n-1： 找出dp[ i-1 ]中的最小值min1、次小值min2，以及min1的颜色idx。 对于每个颜色j： 如果j != idx，则dp[ i][ j] = min1 + costs[ i][ j ] 否则dp[ i][ j] = min2 + costs[ i][ j ] 最终答案：min(dp[ n-1][ j ])，j从0到k-1。 空间优化 由于dp[ i]只依赖于dp[ i-1]，可以只用一个一维数组prev来保存前一行的结果，将空间复杂度从O(n* k)降为O(k)。 总结 本题的关键在于利用最小值和次小值的预处理，避免了对每个颜色j都遍历k种颜色，从而将复杂度从O(n k²)优化到O(n k)。这种优化技巧在相邻状态有颜色限制的动态规划中非常常见。