动态规划解决粉刷房子问题：算法与优化

1. 问题背景与需求分析

最近在刷算法题时遇到一个经典的动态规划问题——粉刷房子。题目要求我们为排成一排的n栋房子选择粉刷颜色，每栋房子可以涂红、蓝、绿三种颜色，相邻房子颜色不能相同。每种颜色在不同房子上的粉刷成本不同，我们需要找出总成本最低的方案。

这个问题看似简单，但蕴含着典型的动态规划思想。作为一名经常处理优化问题的开发者，我发现这类题目在实际开发中也有广泛应用场景，比如资源分配、路径规划等。理解这个问题的解法，对提升算法思维很有帮助。

2. 动态规划思路拆解

2.1 问题建模

首先我们需要将问题抽象为数学模型。给定一个n×3的costs矩阵，其中costs[i][j]表示第i栋房子刷成颜色j的成本（j=0,1,2分别对应红、蓝、绿）。我们的目标是找到一个颜色序列，满足相邻颜色不同，且总成本最小。

2.2 状态定义

动态规划的核心是状态定义。这里我们定义dp[i][j]表示刷到第i栋房子时，选择颜色j的最小总成本。这个状态定义抓住了问题的两个关键维度：

• 房子序号i：表示处理进度
• 颜色j：表示当前决策

2.3 状态转移方程

根据题意，当前房子颜色不能与前一个相同。因此状态转移方程为：

code复制dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i-1][0]  // 当前选红色
dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i-1][1]  // 当前选蓝色  
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i-1][2]  // 当前选绿色

这个方程表示当前选择某种颜色时，前一个房子只能从另外两种颜色中选成本较小的。

2.4 初始化与边界处理

初始状态处理很关键。我们可以选择：

1. 直接初始化dp[0][j] = costs[0][j]
2. 添加虚拟节点，让dp[0][j]=0

这里采用第二种方法，增加一个虚拟的0号房子，这样实际房子从1开始编号，代码实现更统一。这也是动态规划中常用的技巧。

3. 代码实现详解

3.1 完整代码实现

cpp复制class Solution {
public:
    int min