将数组划分为最少子数组且各子数组和在[w, W]区间的求解问题

前置校验 #

如果数组中存在任意单个元素的值大于上限W，问题直接无解，因为无法拆分单个元素，必然会出现某段和超过W。

动态规划实现（无需二维状态，一维即可） #

• 状态定义：dp[i]表示处理完原数组前i个元素（对应下标0 ~ i-1）时，满足条件的最少划分数
• 初始状态：dp[0] = 0（空数组无需划分），其余dp[i]初始化为无穷大，表示初始状态下该位置无法完成合法划分
• 前缀和预处理：先计算前缀和数组pre，其中pre[0] = 0，pre[i] = pre[i-1] + nums[i-1]，方便快速计算任意区间的元素和
• 状态转移逻辑：
  对于每个位置i（从1到数组长度n），遍历所有小于i的j，如果区间[j, i-1]的元素和pre[i] - pre[j]落在区间[w, W]内，则更新dp[i] = min(dp[i], dp[j] + 1)
• 最终结果：如果dp[n]仍为无穷大则返回-1表示无解，否则dp[n]就是最少划分数量

效率优化（仅适用于数组元素全为正数的场景，也是绝大多数题目的隐含前提） #

元素全为正的前提下，前缀和是严格单调递增的，因此对于每个i，符合条件的j是连续的区间：
pre[i] - W ≤ pre[j] ≤ pre[i] - w
可以通过二分查找快速定位j的左右边界，再配合单调队列维护区间内dp[j]的最小值，时间复杂度可以从基础版的O(n²)降到O(n)或O(nlogn)。
如果数组存在负数元素，前缀和不具备单调性，无法使用上述优化，只能使用基础DP实现。

基础版示例代码（Python） #

def min_subarray_split(nums, w, W):
    n = len(nums)
    # 前置校验：单个元素超过W直接无解
    for num in nums:
        if num > W:
            return -1
    # 预处理前缀和
    pre_sum = [0] * (n + 1)
    for i in range(1, n + 1):
        pre_sum[i] = pre_sum[i - 1] + nums[i - 1]
    
    INF = float('inf')
    dp = [INF] * (n + 1)
    dp[0] = 0
    
    for i in range(1, n + 1):
        for j in range(i):
            current_sum = pre_sum[i] - pre_sum[j]
            if w <= current_sum <= W:
                dp[i] = min(dp[i], dp[j] + 1)
    
    return dp[n] if dp[n] != INF else -1

内容的提问来源于stack exchange，提问作者AQN