如何实现相邻元素对选元素的最小成本计算及所选元素记录

要在计算最小成本的同时记录所选元素，核心是在动态规划过程中记录状态转移的路径，最后通过回溯路径得到选中的元素。以下是修改后的实现方案：

思路说明 #

1. 保留原有的min_sum数组记录选中第i个元素时的最小总成本，新增prev数组记录每个位置的转移来源（即选中当前元素时，前一个选中的元素索引）。
2. 状态转移时，不仅计算最小成本，还要记录当前选择是来自i-1还是i-2。
3. 确定最终的末尾选中位置：比较最后两个位置的最小成本，选择成本更低的那个位置作为回溯起点。
4. 通过prev数组回溯，收集所有选中的元素，反转后得到从左到右的选择顺序。

修改后的代码 #

arr = [50, 30, 40, 60, 10, 30, 10]
n = len(arr)

if n < 2:
    print(f"最小成本：{arr[0]}，所选元素：{[arr[0]]}")
else:
    min_sum = [0] * n
    prev = [-1] * n  # 记录每个选中位置的前一个选中索引

    min_sum[0] = arr[0]
    min_sum[1] = arr[1]

    for i in range(2, n):
        choice1 = min_sum[i-1] + arr[i]
        choice2 = min_sum[i-2] + arr[i]
        if choice1 <= choice2:
            min_sum[i] = choice1
            prev[i] = i-1
        else:
            min_sum[i] = choice2
            prev[i] = i-2

    # 确定最后一个选中的位置
    last_idx = n-1 if min_sum[-1] <= min_sum[-2] else n-2

    # 回溯收集所选元素
    selected = []
    current_idx = last_idx
    while current_idx >= 0:
        selected.append(arr[current_idx])
        current_idx = prev[current_idx]
        if current_idx == -1:
            break

    # 反转得到从左到右的选择顺序
    selected.reverse()
    total_cost = min(min_sum[-1], min_sum[-2])

    print(f"最小成本：{total_cost}")
    print(f"所选元素：{selected}")

测试结果 #

• 示例1输入[50, 30, 40, 60, 10, 30, 10]，输出：

  最小成本：90
  所选元素：[30, 40, 10, 10]
  

• 示例2输入[60, 100, 70]，输出：

  最小成本：100
  所选元素：[100]
  

内容的提问来源于stack exchange，提问作者NitaStack