动态规划求解相邻元素选值最小和：如何输出选中元素

问题描述 #

给定整数数组，要求每对相邻元素中至少选择一个，找到所选元素的最小总和，并输出该总和及所有选中元素。
示例：

• 数组{1,0,5}：最小总和为0，选中元素是0；
• 数组{10,30,90,50,30}：最小总和为80，选中元素是30、50。

用户已尝试用动态规划计算最小总和，但无法输出选中元素，当前Java代码如下：

public static void main(String[] args) {
        // Define the input array
        int[] arr = {50, 30, 40, 60, 10, 30, 10};
        // Define the array to store the minimum sum for each index
        int[] dp = new int[arr.length];
        // Initialize the first element of the dp array
        dp[0] = arr[0];
        dp[1] = arr[1];
        // Loop over the input array from the second index to the last index
        int choice1 = 0, choice2;
        for(int i = 2; i<arr.length; i++) {
            // Choose the previous index and add its minimum sum to the current element
             choice1 = dp[i-1] + arr[i];
            // Choose the index before the previous index and add its minimum sum to the current element
             choice2 = dp[i-2] + arr[i];
            // Compare the two choices and choose the one with the lower sum
             dp[i] = Math.min(choice1, choice2);
        }
        // Print the minimum sum and the chosen values
        if(dp[arr.length - 1] > dp[arr.length - 2]) {
            System.out.println(dp[arr.length - 2]);
        }else {
            System.out.println(dp[arr.length - 1]);
        }
    }

问题分析 #

原代码的动态规划逻辑存在错误：它默认每次必须选择当前元素，但实际上我们可以不选当前元素（只要前一个元素被选中即可），这会导致计算出的最小总和不准确（比如示例1会得到错误结果）。

要同时得到最小总和和选中元素，我们需要：

1. 修正动态规划的状态定义，确保逻辑正确；
2. 额外维护路径记录，标记每个元素是否被选中；
3. 通过回溯推导选中的元素。

修正后的解决方案 #

我们使用两个状态数组分别记录选中当前元素和不选中当前元素时的最小总和，同时用布尔数组记录选择路径：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class MinSumSelection {
    public static void main(String[] args) {
        int[] arr = {50, 30, 40, 60, 10, 30, 10};
        int n = arr.length;
        if (n == 0) {
            System.out.println("最小总和：0，选中元素：无");
            return;
        }

        // take[i]：选中第i个元素时，前i+1个元素的最小总和
        int[] take = new int[n];
        // notTake[i]：不选中第i个元素时，前i+1个元素的最小总和（此时必须选中第i-1个元素）
        int[] notTake = new int[n];
        // 记录每个位置是否被选中
        boolean[] selected = new boolean[n];

        // 初始化第一个元素
        take[0] = arr[0];
        selected[0] = true;
        // 单个元素不选的话，没有相邻对，满足条件，总和为0
        notTake[0] = 0;

        for (int i = 1; i < n; i++) {
            // 选中当前元素：取前一个元素选或不选的最小值，加上当前元素值
            take[i] = Math.min(take[i-1], notTake[i-1]) + arr[i];
            // 不选中当前元素：必须选中前一个元素，所以取前一个元素选中时的总和
            notTake[i] = take[i-1];
        }

        // 确定最小总和
        int minTotal = Math.min(take[n-1], notTake[n-1]);
        System.out.println("最小总和：" + minTotal);

        // 回溯推导选中的元素
        List<Integer> result = new ArrayList<>();
        int i = n - 1;
        // 从最后一个元素开始判断是否被选中
        while (i >= 0) {
            if (i == 0) {
                // 第一个元素：如果选中状态对应的总和等于minTotal，则选中
                if (take[i] == minTotal) {
                    result.add(arr[i]);
                    selected[i] = true;
                }
                break;
            }
            // 判断当前元素是否被选中：如果take[i]等于minTotal，说明选中当前元素
            if (take[i] == minTotal) {
                result.add(arr[i]);
                selected[i] = true;
                // 向前回溯，减去当前元素的数值，找前序状态
                minTotal -= arr[i];
                i--;
            } else {
                // 当前元素不被选中，那么前一个元素必须被选中
                result.add(arr[i-1]);
                selected[i-1] = true;
                minTotal = notTake[i];
                i -= 2;
            }
        }

        // 反转列表，得到从左到右的选中元素顺序
        Collections.reverse(result);
        System.out.println("选中元素：" + result);
    }
}

代码说明 #

1. 状态定义：
   • take[i]：选中第i个元素时，前i+1个元素的最小总和；
   • notTake[i]：不选中第i个元素时，前i+1个元素的最小总和（此时必须选中第i-1个元素）。
2. 路径记录：通过selected数组标记元素是否被选中，最后从后往前回溯推导选中的元素。
3. 回溯逻辑：从最后一个元素开始，根据take和notTake的值判断当前元素是否被选中，逐步向前推导，最后反转列表得到正确顺序。

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