本文介绍如何用空间高效的一维动态规划替代多维数组，解决“给定任意数量候选整数，求和为目标值且元素个数最少的组合”问题，适用于基数数组长度未知的通用场景。
本文介绍如何用空间高效的一维动态规划替代多维数组，解决“给定任意数量候选整数，求和为目标值且元素个数最少的组合”问题，适用于基数数组长度未知的通用场景。
该问题本质是经典的最少硬币数凑目标和问题（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<Integer> 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<Integer> 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<Integer> 存储所有可行前驱；
- 进阶优化：对大规模 target，可结合 BFS（按和值层级扩展）或 A* 启发式搜索进一步加速，但一维 DP 已满足绝大多数工程需求。
该方案彻底摆脱了“维度依赖”，以清晰的状态定义和线性空间开销，优雅支撑任意长度的基数输入，是动态规划中“降维打击”的典型实践。
