如何用Java实现可变维度动态规划求解整数最优组合求和问题

给定一组唯一的基数整数和目标值，返回元素数量最少的基数整数组合，使其和等于目标值。

示例 #

Example 1 #

Given: baseIntegers = [4, 7]; target = 15;
Return: [7, 4, 4]
Explanation: 7+4+4=15.

Example 2 #

Given: baseIntegers = [3, 5, 7]; target = 18;
Return: [7, 5, 3, 3]
Explanation: 7+5+3+3=18. [3, 3, 3, 3, 3] is not returned since it contains 1 more element than [7, 5, 3, 3]

Example 3 #

Given: baseIntegers = [5, 6, 8, 11]; target = 52;
Return: [11, 11, 11, 11, 8]
Explanation: 11+11+11+11+8=52.

Example 4 #

Given: baseIntegers = [2, 5]; target = 3;
Return: []
Explanation: 2,5 do not add up to 3.

现有解法 #

本人已通过**Dynamic Programming（动态规划）**解决固定长度基数的情况，例如针对基数长度为2的场景创建二维数组存储求和过程：

sum[0,0] = 0
sum[1,0] = sum[0,0]+4 = 4
sum[1,1] = sum[1,0]+7 = 11
sum[2,1] = sum[1,1]+4 = 15

找到目标和后，可从维度[2,1]（2个4和1个7）获取结果。

需求与困惑 #

但当baseIntegers长度未知时，无法提前创建对应维度的多维数组，因此寻求Java下解决该可变输入长度问题的方法。

内容的提问来源于stack exchange，提问作者WAN YIN LEUNG