本文详细探讨了如何在满足相邻房屋花卉颜色不同的约束下，为N座房屋选择花卉颜色以实现最低总种植成本的问题。针对暴力枚举方法在处理大规模数据时效率低下和内存溢出的问题，本文提出并详细阐述了基于动态规划的优化解决方案。通过状态定义、状态转移方程的推导，并提供Python代码示例，展示了如何高效计算最小成本以及如何回溯重建最优种植方案。
假设一条街上有N座房屋，每座房屋的花园可以种植三种颜色（例如，白、黄、红）花卉中的一种。我们获得了一个价格列表，其中每行代表一座房屋，每列代表一种花卉颜色对应的种植成本。例如：
9 2 7 5 8 3 4 7 8 ... 3 5 2
这里的目标是找到一种种植方案，使得N座房屋的总种植成本最低，同时必须满足一个关键约束：相邻的房屋不能种植相同颜色的花卉。
一个简单的例子是，对于四座房屋的价格列表：
房屋\颜色 白 黄 红 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。
最初，解决此问题的一种直观方法是使用穷举搜索。例如，在Python中，可以使用 itertools.product 生成所有可能的颜色组合（每座房屋有3种选择，N座房屋就有 3^N 种组合）。然后，对每种组合进行检查，排除掉相邻房屋颜色相同的无效组合，最后计算剩余有效组合的总成本并找出最小值。
然而，这种方法存在显著的性能问题。当房屋数量N较大时（例如N > 20），3^N 会迅速增长到一个天文数字。生成并存储如此大量的组合将导致：
因此，我们需要一种更高效的算法来解决这个问题。
动态规划（Dynamic Programming, DP）是解决这类具有重叠子问题和最优子结构性质的优化问题的有效方法。通过构建子问题的最优解来逐步推导出原问题的最优解，避免了重复计算。
动态规划的核心思想是，对于第 i 座房屋，其最优选择取决于第 i-1 座房屋的最优选择。由于第 i 座房屋的颜色不能与第 i-1 座房屋的颜色相同，我们可以根据第 i-1 座房屋选择不同颜色时的最小成本来决定第 i 座房屋的最佳选择。
我们定义 dp[i][color_index] 为考虑前 i+1 座房屋（从0到i），且第 i 座房屋选择 color_index 颜色时的最小累计成本。 这里，color_index 可以是0、1、2，分别代表三种不同的花卉颜色。
假设 cost[i][j] 表示第 i 座房屋选择第 j 种颜色的成本。 对于第 i 座房屋（i > 0）：
对于第一座房屋（i = 0）： dp[0][0] = cost[0][0]dp[0][1] = cost[0][1]dp[0][2] = cost[0][2]
最终的最小总成本将是 min(dp[N-1][0], dp[N-1][1], dp[N-1][2])。
以下是使用动态规划解决此问题的Python实现。为了便于理解，我们将分两步展示：首先是仅计算最小总成本，然后是同时重建最优路径。
这种实现方式利用了动态规划的状态压缩技巧，只需要存储上一行的状态即可计算当前行的状态，从而将空间复杂度优化到 O(1)。
def solve_min_cost(rows):
"""
计算满足相邻房屋颜色不同约束下的最小总种植成本。
Args:
rows: 一个列表的列表，其中每个子列表代表一座房屋的三种花卉颜色成本。
例如: [[5, 6, 7], [3, 7, 9], [6, 7, 3], [1, 8, 4]]
Returns:
最小总种植成本。
"""
# 初始化第一座房屋的成本
# a, b, c 分别代表当前房屋选择颜色0, 1, 2时的最小累计成本
# 初始时，它们就是第一座房屋的成本
a, b, c = 0, 0, 0
# 遍历每一座房屋的成本
for x, y, z in rows:
# 计算当前房屋选择颜色0时的最小累计成本
# 它的前一座房屋必须选择颜色1或颜色2
new_a = min(b, c) + x
# 计算当前房屋选择颜色1时的最小累计成本
# 它的前一座房屋必须选择颜色0或颜色2
new_b = min(a, c) + y
# 计算当前房屋选择颜色2时的最小累计成本
# 它的前一座房屋必须选择颜色0或颜色1
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_example = [
[5, 6, 7],
[3, 7, 9],
[6, 7, 3],
[1, 8, 4]
]
print(f"最小总成本: {solve_min_cost(rows_example)}") # 输出: 最小总成本: 13为了重建具体的颜色选择路径，我们需要在动态规划过程中不仅存储最小成本，还要存储达到该成本所经过的路径信息。这通常通过存储一个元组 (cost, path_info) 来实现。
def solve_with_path(rows):
"""
计算满足相邻房屋颜色不同约束下的最小总种植成本，并返回对应的颜色选择路径。
Args:
rows: 一个列表的列表，其中每个子列表代表一座房屋的三种花卉颜色成本。
例如: [[5, 6, 7], [3, 7, 9], [6, 7, 3], [1, 8, 4]]
Returns:
一个元组 (最小总成本, 颜色选择路径列表)。
颜色选择路径列表中的元素为1, 2, 3，分别代表三种花卉颜色。
"""
# 初始化第一座房屋的成本和路径
# a, b, c 分别存储 (成本, 路径信息)
# 路径信息使用 (当前颜色索引, 上一个路径) 的嵌套元组表示
a = (0, None) # 0代表颜色1
b = (0, None) # 0代表颜色2
c = (0, None) # 0代表颜色3
def extend(prev_cost_path1, prev_cost_path2, current_color_cost, current_color_index):
"""
辅助函数，用于计算当前房屋选择指定颜色时的最小累计成本和路径。
Args:
prev_cost_path1: 前一座房屋选择颜色1时的 (成本, 路径)
prev_cost_path2: 前一座房屋选择颜色2时的 (成本, 路径)
current_color_cost: 当前房屋选择指定颜色的成本
current_color_index: 当前房屋选择的颜色索引 (1, 2, 或 3)
Returns:
(新的最小累计成本, 新的路径信息)
"""
# 比较前一座房屋选择两种不同颜色时的成本，取最小值
min_sum, min_path = min(prev_cost_path1, prev_cost_path2)
# 计算当前累计成本，并记录当前颜色和之前的路径
return min_sum + current_color_cost, (current_color_index, min_path)
# 遍历每一座房屋的成本
for x, y, z in rows: # x, y, z 分别对应颜色1, 2, 3的成本
# 计算当前房屋选择颜色1时的 (成本, 路径)
# 前一座房屋必须选择颜色2或颜色3
a, b, c = (
extend(b, c, x, 1), # 当前房屋选颜色1
extend(a, c, y, 2), # 当前房屋选颜色2
extend(a, b, z, 3) # 当前房屋选颜色3
)
# 所有房屋处理完毕后，a, b, c 包含最后一座房屋选择不同颜色的 (最小累计成本, 路径)
# 取三者中的最小值即为总的最小成本和最终路径
total_sum, path_info = min(a, b, c)
# 重建路径：从后向前遍历路径元组
flat_path = []
while path_info:
color_index, path_info = path_info
flat_path.append(color_index)
# 路径是逆序存储的，需要反转
return total_sum, flat_path[::-1]
# 示例数据
rows_example = [
[5, 6, 7],
[3, 7, 9],
[6, 7, 3],
[1, 8, 4]
]
total_cost, path = solve_with_path(rows_example)
print(f"最小总成本: {total_cost}, 颜色路径: {path}") # 输出: 最小总成本: 13, 颜色路径: [2, 1, 3, 1]在上述代码中，颜色索引 1, 2, 3 是为了与问题描述中的颜色概念对应，它们在内部逻辑中可以被视为抽象的颜色标识符。
通过采用动态规划，我们成功地将一个在N较大时无法解决的问题转化为了一个高效且可扩展的解决方案。
以上就是优化房屋花卉种植成本：动态规划算法实践的详细内容，更多请关注php中文网其它相关文章！
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移，垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是，许多工具可以让 Windows 保持平稳运行。
广告Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
600
收藏
