动态规划解决带相邻约束的花园种植成本优化问题

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)}") # 输出: 13

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] (代表黄, 白, 红, 白)