将一个数组分成最小数量的 sub-arrays 使得每个子数组的总和在 [w, W] 范围内
Divide an array into minimum number of sub-arrays such that each subarray have sum in the range [w, W]
我正在尝试解决以下问题（与标题相同）：将数组划分为最小数量的 sub-arrays 使得每个子数组的总和在 [w, W] 范围内，注意你可以' 重新排序数组。我想我需要在 2D 状态下使用 DP space，但我似乎不太明白。
如有任何帮助，我们将不胜感激！
一个一维数组就足够了。称它为 arr，令 arr[i] 代表同一问题的解决方案仅限于前 i 个元素。
初始化 arr[i] = i 的无穷大 s.t。直到 & 包括 i 的元素的总和 < w，如果总和 >= w 且 <= W.
则为 1
通过考虑所有以 i 结尾的有效子数组，以升序求解 i 的每个未知值，为有效子数组开始之前的最后一个 elt 取所有这些存储在 arr 中的最小值，并递增1.
例如w=3, W=5, 输入 = 2,2,3,4,2,1,1,5
initialize: arr = [inf, 1, ...]
input[2]: arr = [inf, 1, 2, ...]
input[3]: arr = [inf, 1, 2, 3, ...]
input[4]: arr = [inf, 1, 2, 3, inf, ...]
input[5]: arr = [inf, 1, 2, 3, inf, 4, ...]
input[6]: arr = [inf, 1, 2, 3, inf, 4, 4, ...]
input[7]: arr = [inf, 1, 2, 3, inf, 4, 4, 5]
解法：[2,2], [3], [4], [2,1,1], [5]
我正在尝试解决以下问题（与标题相同）：将数组划分为最小数量的 sub-arrays 使得每个子数组的总和在 [w, W] 范围内，注意你可以' 重新排序数组。我想我需要在 2D 状态下使用 DP space，但我似乎不太明白。
如有任何帮助，我们将不胜感激！
一个一维数组就足够了。称它为 arr，令 arr[i] 代表同一问题的解决方案仅限于前 i 个元素。
初始化 arr[i] = i 的无穷大 s.t。直到 & 包括 i 的元素的总和 < w，如果总和 >= w 且 <= W.
则为 1通过考虑所有以 i 结尾的有效子数组，以升序求解 i 的每个未知值，为有效子数组开始之前的最后一个 elt 取所有这些存储在 arr 中的最小值，并递增1.
例如w=3, W=5, 输入 = 2,2,3,4,2,1,1,5
initialize: arr = [inf, 1, ...]
input[2]: arr = [inf, 1, 2, ...]
input[3]: arr = [inf, 1, 2, 3, ...]
input[4]: arr = [inf, 1, 2, 3, inf, ...]
input[5]: arr = [inf, 1, 2, 3, inf, 4, ...]
input[6]: arr = [inf, 1, 2, 3, inf, 4, 4, ...]
input[7]: arr = [inf, 1, 2, 3, inf, 4, 4, 5]
解法：[2,2], [3], [4], [2,1,1], [5]