本文详细介绍如何使用动态规划解决一个经典的优化问题：在一条街上为N栋房屋种植鲜花，每栋房屋有3种花色可选，且相邻房屋不能种植同色鲜花。文章首先阐述了问题的背景及暴力解法的局限性，随后深入讲解了动态规划的核心思想，并通过Python示例代码展示了如何高效计算最低总成本，以及如何回溯并获取具体的种植方案，显著提升了大规模问题的求解效率。
问题描述
假设一条街上有N栋房屋，每栋房屋的花园可以种植三种不同颜色的鲜花（例如，白色、黄色、红色）。对于每栋房屋，每种颜色的鲜花都有其对应的种植成本。这些成本通常以矩阵形式给出，其中每一行代表一栋房屋，每一列代表一种花色。
核心约束条件： 如果一栋房屋种植了某种颜色的鲜花，那么其相邻的房屋不能种植相同颜色的鲜花。
我们的目标是找到一种种植方案，使得所有房屋的鲜花种植总成本最低，同时满足上述相邻约束。
示例： 考虑4栋房屋的成本矩阵：
| 房屋/花色 | 白色 | 黄色 | 红色 |
|---|---|---|---|
| H1 | 5 | 6 | 7 |
| H2 | 3 | 7 | 9 |
| H3 | 6 | 7 | 3 |
| H4 | 1 | 8 | 4 |
根据规则，最便宜的方案可能是：H1-黄色(6), H2-白色(3), H3-红色(3), H4-白色(1)，总成本为 6 + 3 + 3 + 1 = 13。
暴力解法的局限性
一个直观但效率低下的方法是枚举所有可能的种植组合。对于N栋房屋和3种花色，总共有 $3^N$ 种组合。然后，对每种组合进行检查，排除不符合相邻约束的组合，并计算其余组合的总成本，最终找出最低成本。
例如，可以使用 itertools.product([1, 2, 3], repeat=n) 生成所有长度为N的颜色序列（1、2、3分别代表三种颜色）。之后，遍历这些序列，去除相邻元素相同的序列，再计算剩余序列的成本。
然而，当N值较大时（例如N > 20），$3^N$ 会迅速增长，导致：
- 内存错误： 生成所有组合可能耗尽系统内存。
- 时间复杂度过高： 遍历并检查大量组合会非常耗时，导致程序运行缓慢甚至崩溃。
因此，我们需要一种更高效的算法来解决这个问题。
动态规划解决方案
动态规划是解决这类优化问题的有效方法，它通过将大问题分解为相互重叠的子问题来避免重复计算。
核心思想
我们可以定义一个状态 dp[i][color] 表示在处理到第 i 栋房屋时，第 i 栋房屋种植 color 颜色鲜花所能达到的最低总成本。
由于第 i 栋房屋的颜色不能与其前一栋房屋（第 i-1 栋）的颜色相同，所以 dp[i][color] 的值将取决于 dp[i-1][other_color1] 和 dp[i-1][other_color2] 的最小值，再加上第 i 栋房屋种植 color 的成本。
状态定义与转移方程
设 costs[i][j] 为第 i 栋房屋种植第 j 种颜色的成本（j 可以是 0, 1, 2）。 我们维护三个变量 a, b, c，分别代表当前房屋种植第一、第二、第三种颜色鲜花时，到目前为止的最低总成本。
对于第 i 栋房屋：
- 如果第 i 栋房屋种植第一种颜色 (color_0)： 其前一栋房屋（第 i-1 栋）必须种植第二种颜色 (color_1) 或第三种颜色 (color_2)。 因此，dp[i][color_0] = min(dp[i-1][color_1], dp[i-1][color_2]) + costs[i][0]
- 如果第 i 栋房屋种植第二种颜色 (color_1)： 其前一栋房屋（第 i-1 栋）必须种植第一种颜色 (color_0) 或第三种颜色 (color_2)。 因此，dp[i][color_1] = min(dp[i-1][color_0], dp[i-1][color_2]) + costs[i][1]
- 如果第 i 栋房屋种植第三种颜色 (color_2)： 其前一栋房屋（第 i-1 栋）必须种植第一种颜色 (color_0) 或第二种颜色 (color_1)。 因此，dp[i][color_2] = min(dp[i-1][color_0], dp[i-1][color_1]) + costs[i][2]
空间优化
注意到计算 dp[i] 时只依赖于 dp[i-1] 的值，我们可以将空间复杂度从 O(N) 优化到 O(1)，只存储前一个房屋的三种颜色最低成本。
初始化： 对于第一栋房屋（索引 0），a = costs[0][0], b = costs[0][1], c = costs[0][2]。 实际上，为了简化代码，我们可以将 a, b, c 初始化为0，然后从第一个房屋的成本开始迭代，效果相同。
1. 只计算最低总成本
以下Python代码实现了只计算最低总成本的动态规划：
def solve_min_cost(rows):
"""
计算满足相邻约束的最低花卉种植总成本。
:param rows: 列表的列表，每行代表一栋房屋，包含三种花色的成本。
例如: [[5, 6, 7], [3, 7, 9], ...]
:return: 最低的种植总成本。
"""
# a, b, c 分别代表当前房屋种植第一、第二、第三种颜色时，到目前为止的最低总成本
# 初始化为0，迭代从第一个房屋开始。
a = b = c = 0
for x, y, z in rows: # x, y, z 分别是当前房屋三种花色的成本
# 计算当前房屋种植第一种颜色 (x) 的最低成本
# 它必须从前一个房屋种植第二种 (b) 或第三种 (c) 颜色中选择成本最低的
new_a = min(b, c) + x
# 计算当前房屋种植第二种颜色 (y) 的最低成本
# 它必须从前一个房屋种植第一种 (a) 或第三种 (c) 颜色中选择成本最低的
new_b = min(a, c) + y
# 计算当前房屋种植第三种颜色 (z) 的最低成本
# 它必须从前一个房屋种植第一种 (a) 或第二种 (b) 颜色中选择成本最低的
new_c = min(a, b) + z
# 更新 a, b, c 为当前房屋的最低成本
a, b, c = new_a, new_b, new_c
# 遍历完所有房屋后，a, b, c 分别是最后一栋房屋种植三种颜色时的最低总成本
# 取三者中的最小值即为全局最低总成本
return min(a, b, c)
# 示例数据
rows_data = [
[5, 6, 7],
[3, 7, 9],
[6, 7, 3],
[1, 8, 4]
]
print(f"最低总成本: {solve_min_cost(rows_data)}") # 输出: 132. 同时获取最低总成本和具体种植方案
为了获取具体的种植方案，我们需要在动态规划过程中不仅存储最低成本，还要存储导致该成本的路径信息。这可以通过存储 (成本, 路径) 对来实现。路径可以是一个元组或列表，记录了从第一栋房屋到当前房屋的颜色选择。
def solve_with_path(rows):
"""
计算满足相邻约束的最低花卉种植总成本，并返回具体的种植方案。
:param rows: 列表的列表，每行代表一栋房屋，包含三种花色的成本。
:return: 一个元组 (最低总成本, 种植方案列表)。
种植方案列表中的元素为1, 2, 3，分别代表三种花色。
"""
# a, b, c 分别存储 (成本, 路径) 对
# 路径用 (当前房屋颜色索引, 前一个房屋的路径) 的元组表示，方便回溯
# 初始化时，成本为0，路径为None
a = b = c = (0, None)
def extend(prev_a, prev_b, current_cost, current_color_index):
"""
辅助函数：根据前一房屋两种不同颜色状态的最小值，计算当前房屋的 (成本, 路径) 对。
:param prev_a: 前一房屋状态A的 (成本, 路径) 对
:param prev_b: 前一房屋状态B的 (成本, 路径) 对
:param current_cost: 当前房屋种植指定颜色的成本
:param current_color_index: 当前房屋种植的颜色索引 (1, 2, 或 3)
:return: 当前房屋的 (成本, 路径) 对
"""
# 比较前一房屋两种不同颜色状态的成本，选择较小的那个
sum_val, path = min(prev_a, prev_b)
# 返回新的 (总成本, 新路径)
# 新路径是 (当前颜色索引, 前一个房屋的路径)
return sum_val + current_cost, (current_color_index, path)
for x, y, z in rows: # x, y, z 是当前房屋三种花色的成本
# 计算当前房屋种植第一种颜色 (x) 的 (成本, 路径)
new_a = extend(b, c, x, 1) # 1 代表第一种颜色
# 计算当前房屋种植第二种颜色 (y) 的 (成本, 路径)
new_b = extend(a, c, y, 2) # 2 代表第二种颜色
# 计算当前房屋种植第三种颜色 (z) 的 (成本, 路径)
new_c = extend(a, b, z, 3) # 3 代表第三种颜色
# 更新 a, b, c
a, b, c = new_a, new_b, new_c
# 遍历完所有房屋后，a, b, c 包含了所有以不同颜色结束的最低总成本及路径
# 找到三者中总成本最低的那个
total_sum, path_tuple = min(a, b, c)
# 从路径元组中回溯并展平路径
flat_path = []
while path_tuple:
color_index, path_tuple = path_tuple
flat_path.append(color_index)
# 路径是从后往前构建的，需要反转以得到正确的顺序
return total_sum, flat_path[::-1]
# 示例数据
rows_data = [
[5, 6, 7],
[3, 7, 9],
[6, 7, 3],
[1, 8, 4]
]
min_cost, path = solve_with_path(rows_data)
print(f"最低总成本: {min_cost}") # 输出: 13
print(f"种植方案: {path}") # 输出: [2, 1, 3, 1] (代表黄, 白, 红, 白)复杂度分析
- 时间复杂度： 算法对每栋房屋进行一次迭代，每次迭代内部的操作（比较、加法）都是常数时间。因此，对于N栋房屋，时间复杂度为 O(N)。这比暴力解法的 $O(3^N)$ 有了巨大的提升。
-
空间复杂度：
- 如果只计算最低总成本，我们只需要存储三个变量 (a, b, c)，空间复杂度为 O(1)。
- 如果需要存储并回溯路径，每个 (成本, 路径) 对的路径部分会随着房屋数量的增加而变长。最坏情况下，路径的长度为N。因此，存储路径需要 O(N) 的空间。
总结与注意事项
- 动态规划的优势： 对于这类具有重叠子问题和最优子结构的问题，动态规划能够将指数级的时间复杂度降低到线性级别，从而高效解决大规模问题。
- 问题变体： 这个动态规划模式非常灵活。如果花色数量改变，只需要调整 a, b, c 变量的数量和 extend 函数的逻辑。如果相邻约束条件改变（例如，不能和前两栋房屋颜色相同），状态定义和转移方程也需要相应调整。
- 数据读取： 教程中示例直接使用了Python列表，实际应用中，你需要从文件（如 domy.txt）读取数据并将其转换为 rows 列表的格式。确保正确解析文件中的字符串为整数。
通过采用动态规划，我们能够高效地解决带有相邻约束的花园种植成本优化问题，无论房屋数量N有多大，都能在可接受的时间内找到最优解。
