如何用动态规划（记忆化）优化数组分割最小差算法至低于O(2^n)

我编写了一个递归+记忆化的算法，用于计算将数组分割为两个子数组后的最小和差，示例如下：

• 输入[1,2,2,3,3]，最小差值为1（计算方式：(1+2+2)-(3+3)）
• 输入[1,100,4,2]，最小差值为93（计算方式：100-(1+4+2)）

当前算法的最坏时间复杂度为O(2^n/2)，想进一步优化性能。现有代码如下：

import java.util.Arrays;

public static int minDiffRecursive(int[] nums) {
    int sum = 0;
    
    for(int num : nums) {
        sum += num;
    }
    
    int[][] memo = new int[nums.length][sum];

    for(int[] row : memo) {
        Arrays.fill(row, -1);
    }
    return move(nums, 0, 0, 0, memo);
}

private static int move(int[] nums, int i, int sum1, int sum2, int[][] memo) {
    if(i >= nums.length) return Math.abs(sum1 - sum2); // 遍历结束，返回差值
    if(memo[i][Math.min(sum1, sum2)] > -1) return memo[i][Math.min(sum1, sum2)]; // 利用对称性读取记忆化值

    int add1 = move(nums, i + 1, sum1 + nums[i], sum2, memo); // 将当前元素加入sum1
    int add2 = move(nums, i + 1, sum1, sum2 + nums[i], memo); // 将当前元素加入sum2

    return memo[i][Math.min(sum1, sum2)] = Math.min(add1, add2); // 记录并返回最小差值
}

原代码的核心问题 #

1. 空间冗余：当数组总和较大时，二维记忆数组memo的第二维度会占用大量内存，甚至可能触发OOM。
2. 复杂度未达多项式级别：本质还是基于递归的状态枚举，没有利用问题的子集和本质，无法处理元素较多的场景。

优化方案 #

方案1：转换为0-1背包问题（多项式复杂度） #

这个问题本质等价于寻找一个子集，使其和尽可能接近数组总和的一半，此时两个子数组的和差为总和 - 2*子集和，最小化该值即可。基于此可以用一维DP数组实现，时间复杂度优化至O(n*S)（S为总和的一半）。

实现代码

public static int minDiffDP(int[] nums) {
    int totalSum = 0;
    for (int num : nums) {
        totalSum += num;
    }
    int target = totalSum / 2;
    // dp[j]表示是否能凑出和为j的子集
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;

    for (int num : nums) {
        // 逆序遍历避免重复选择同一元素
        for (int j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }

    // 找到最接近target的可达子集和
    int maxSubsetSum = 0;
    for (int j = target; j >= 0; j--) {
        if (dp[j]) {
            maxSubsetSum = j;
            break;
        }
    }

    return totalSum - 2 * maxSubsetSum;
}

复杂度分析

• 时间复杂度：O(n*S)，n为数组长度，S为总和的一半，相比原指数级复杂度大幅提升。
• 空间复杂度：O(S)，相比原二维数组大幅压缩。

方案2：BitSet优化空间 #

如果数组总和不是极大，可以用BitSet存储可达的子集和，进一步节省内存：

import java.util.BitSet;

public static int minDiffBitSet(int[] nums) {
    int totalSum = 0;
    BitSet bitSet = new BitSet();
    bitSet.set(0);

    for (int num : nums) {
        totalSum += num;
        // 合并现有可达和与现有和+当前num的结果
        bitSet.or(bitSet.get(num, bitSet.size()));
    }

    int target = totalSum / 2;
    // 找到最接近target的可达和
    int maxSubsetSum = bitSet.previousSetBit(target);
    return totalSum - 2 * maxSubsetSum;
}

方案3：双向搜索（Meet-in-the-Middle）处理大数组 #

当数组长度n>40时，O(n*S)可能仍不够高效，此时可以用双向搜索拆分计算：

1. 将数组分为前后两半，分别生成所有可能的子集和。
2. 对其中一半的子集和排序，遍历另一半时用二分查找匹配最接近目标的值。

实现代码

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

public static int minDiffMeetInMiddle(int[] nums) {
    int totalSum = 0;
    for (int num : nums) {
        totalSum += num;
    }
    int target = totalSum / 2;

    // 分割数组
    int mid = nums.length / 2;
    List<Integer> leftSums = generateSubsetSums(nums, 0, mid);
    List<Integer> rightSums = generateSubsetSums(nums, mid, nums.length);

    // 排序右半部分子集和
    Collections.sort(rightSums);

    int minDiff = Integer.MAX_VALUE;
    for (int leftSum : leftSums) {
        int remaining = target - leftSum;
        // 二分查找最接近remaining的值
        int idx = Collections.binarySearch(rightSums, remaining);
        if (idx >= 0) {
            // 找到精确匹配，直接返回最小可能差值
            return totalSum - 2 * (leftSum + remaining);
        } else {
            idx = -idx - 1;
            // 检查相邻位置的候选值
            if (idx < rightSums.size()) {
                minDiff = Math.min(minDiff, Math.abs(totalSum - 2 * (leftSum + rightSums.get(idx))));
            }
            if (idx > 0) {
                minDiff = Math.min(minDiff, Math.abs(totalSum - 2 * (leftSum + rightSums.get(idx - 1))));
            }
        }
    }
    return minDiff;
}

// 生成指定区间内的所有子集和
private static List<Integer> generateSubsetSums(int[] nums, int start, int end) {
    List<Integer> sums = new ArrayList<>();
    sums.add(0);
    for (int i = start; i < end; i++) {
        int num = nums[i];
        int size = sums.size();
        for (int j = 0; j < size; j++) {
            sums.add(sums.get(j) + num);
        }
    }
    return sums;
}

复杂度分析

• 时间复杂度：O(n*2^{(n/2))，生成子集和为O(2}(n/2))，排序与二分查找为O(2^(n/2)*log(2(n/2)))，适合n较大的场景（比如n=40时，2^20约1e6，计算量完全可控）。

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