使用一维动态规划求解最少硬币组合问题（可变基数数组的通用解法）

本文介绍如何用空间高效的一维动态规划替代多维数组，解决“给定任意数量候选整数，求和为目标值且元素个数最少的组合”问题，适用于基数数组长度未知的通用场景。

本文介绍如何用空间高效的一维动态规划替代多维数组，解决“给定任意数量候选整数，求和为目标值且元素个数最少的组合”问题，适用于基数数组长度未知的通用场景。

该问题本质是经典的最少硬币数凑目标和问题（Coin Change Problem - Minimum Coins Version）的变体：给定一组正整数（无重复、无限可用），求构成目标值 target 所需的最少元素个数，并重构具体组合。关键挑战在于避免为不同基数长度（如 [4,7] vs [5,6,8,11]）设计维度不固定的多维 DP 表——这不仅实现复杂、内存爆炸（如 10 维 ×10 元素即 10¹⁰ 空间），更违背动态规划“状态压缩”的核心思想。

✅ 正确解法：采用一维 DP + 路径回溯数组，时间复杂度 O(target × n)，空间复杂度 O(target)，完全与输入基数长度 n 无关。

核心思路

• dp[i] 表示凑出和 i 所需的最少元素个数（若不可达则为 Integer.MAX_VALUE）；
• prev[i] 记录达成 i 时最后选用的数字（用于后续回溯构造组合）；
• 状态转移：对每个 i ∈ [1, target]，遍历所有 coin ∈ baseIntegers，若 i ≥ coin 且 dp[i - coin] + 1 < dp[i]，则更新 dp[i] = dp[i - coin] + 1 并设置 prev[i] = coin。

Java 实现（含完整回溯）

import java.util.*;

public class MinCombinationSum {
    public static List minCombination(int[] baseIntegers, int target) {
        if (target == 0) return new ArrayList<>();
        if (baseIntegers == null || baseIntegers.length == 0 || target < 0) 
            return Collections.emptyList();

        // dp[i] = 最少元素个数凑成 i；prev[i] = 达成 i 时最后选的数字
        int[] dp = new int[target + 1];
        int[] prev = new int[target + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        // 动态规划填表
        for (int i = 1; i <= target; i++) {
            for (int coin : baseIntegers) {
                if (coin <= i && dp[i - coin] != Integer.MAX_VALUE) {
                    if (dp[i - coin] + 1 < dp[i]) {
                        dp[i] = dp[i - coin] + 1;
                        prev[i] = coin;
                    }
                }
            }
        }

        // 检查是否可达
        if (dp[target] == Integer.MAX_VALUE) {
            return Collections.emptyList();
        }

        // 回溯构造结果组合
        List result = new ArrayList<>();
        int curr = target;
        while (curr > 0) {
            result.add(prev[curr]);
            curr -= prev[curr];
        }
        return result;
    }

    // 测试示例
    public static void main(String[] args) {
        System.out.println(minCombination(new int[]{4, 7}, 15));     // [4, 4, 7] 或 [7, 4, 4]（顺序取决于遍历顺序）
        System.out.println(minCombination(new int[]{3, 5, 7}, 18));  // [3, 3, 5, 7]
        System.out.println(minCombination(new int[]{5, 6, 8, 11}, 52)); // [8, 11, 11, 11, 11]
        System.out.println(minCombination(new int[]{2, 5}, 3));       // []
    }
}

注意事项与优化点

• 顺序无关性：返回组合顺序取决于 baseIntegers 遍历顺序及更新策略，实际应用中可按需排序或后处理（如 Collections.sort(result)）；
• 数值范围安全：target 过大时需考虑栈/堆内存限制，但相比多维方案已极大降低风险；
• 扩展性：若需所有最优解（而非任一解），可将 prev[i] 改为 List 存储所有可行前驱；
• 进阶优化：对大规模 target，可结合 BFS（按和值层级扩展）或 A* 启发式搜索进一步加速，但一维 DP 已满足绝大多数工程需求。

该方案彻底摆脱了“维度依赖”，以清晰的状态定义和线性空间开销，优雅支撑任意长度的基数输入，是动态规划中“降维打击”的典型实践。