I am trying to solve the following problem (Same as title): Divide an array into minimum number of sub-arrays such that each subarray have sum in the range [w, W], note that you can't reorder the array. I think I would need to use DP with a 2D state space, but I can't seem to quite figure it out.

Any help on this would be appreciated!

CodePudding user response：

A 1d array suffices for DP. Call it arr, and let arr[i] represent the solution to the same problem limited to the first i elements.

Initialize arr[i] = infinity for i s.t. the sum of the elements up to & including i is < w, and 1 if the sum is >= w and <= W.

Solve for each unknown value of i in ascending order by considering all valid subarrays ending with i, taking the min value across all of these stored in arr for the last elt prior to the start of the valid subarray, and incrementing by 1.

E.g. w=3, W=5, input = 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]

Solution: [2,2], [3], [4], [2,1,1], [5]