从洛谷P1281看前缀和在动态规划中的巧妙运用

peach

728人浏览 · 2026-02-11 07:07:13

peach · 2026-02-11 07:07:13 发布

前缀和优化：动态规划中的高效计算艺术

在算法竞赛和编程面试中，动态规划（DP）是解决复杂问题的利器。但当数据规模增大时，传统的动态规划方法往往会因为时间复杂度太高而无法在限定时间内完成计算。这时，前缀和技巧就能大显身手，将原本O(n²)的复杂度优化到O(n)，实现质的飞跃。

1. 前缀和基础与动态规划的结合

前缀和（Prefix Sum）是一种简单却强大的预处理技术。对于一个数组a，我们定义其前缀和数组s，其中s[i]表示a[1]到a[i]的和。这个看似简单的操作，在动态规划问题中却能发挥惊人的优化效果。

前缀和的核心公式：

s[i] = s[i-1] + a[i]  # 一维前缀和
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]  # 二维前缀和

在动态规划中，我们经常需要计算子数组或子矩阵的和。传统方法是遍历求和，时间复杂度为O(n)或O(n²)。而使用前缀和，我们可以将任意区间和的计算优化到O(1)：

sum(l, r) = s[r] - s[l-1]  # 一维区间和
sum(x1,y1,x2,y2) = s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]  # 二维子矩阵和

为什么前缀和能优化动态规划？ 因为动态规划的本质是通过子问题的解来构建更大问题的解，而前缀和恰好提供了快速获取子问题解的能力。

2. 洛谷P1281案例深度解析

让我们以洛谷P1281"书的复制"问题为例，展示前缀和在动态规划中的实际应用。题目要求将m本书分给k个人抄写，每本书有固定的页数，目标是使所有人中抄写页数最多的人抄写的页数最少。

2.1 传统动态规划解法

不使用前缀和时，状态转移需要枚举子段长度：

dp[i][j] = min(dp[i][j], max(dp[h-1][j-1], sum(h,i))) 
# sum(h,i)需要O(n)时间计算

这种解法的时间复杂度为O(m²k)，当m=500，k=500时，计算量将达到上亿次，无法在竞赛时间限制内完成。

2.2 前缀和优化后的解法

引入前缀和数组s后，sum(h,i)可以O(1)计算：

sum(h,i) = s[i] - s[h-1]

优化后的状态转移方程：

dp[i][j] = min(max(dp[h-1][j-1], s[i]-s[h-1]) for h in range(j,i+1))

虽然仍需三重循环，但内层计算从O(n)降到了O(1)，整体复杂度优化到O(m²k)，在m,k≤500时完全可行。

关键优化对比表：

方法	计算sum(h,i)复杂度	总时间复杂度	适用数据规模
传统DP	O(n)	O(m²k)	m,k≤100
前缀和优化	O(1)	O(m²k)	m,k≤500
二分答案	O(n)	O(nlogS)	m≤1e5,k≤1e5

注意：虽然复杂度表示相同，但实际运行时间前缀和优化比传统DP快10倍以上，因为内层操作从加法变成了简单的数组访问。

3. 前缀和优化的适用场景与实现技巧

前缀和优化特别适用于以下动态规划场景：

区间和问题：需要频繁计算子数组或子矩阵的和
分段问题：将序列分成若干段，优化每段的计算
状态转移依赖区间统计：如最大/最小值、平均值等

实现时的三个关键点：

边界处理：前缀和数组通常从1开始索引，s[0]=0
空间优化：有时可以用滚动数组减少空间复杂度
维度扩展：二维甚至更高维前缀和的应用

# 二维前缀和初始化示例
rows, cols = len(matrix), len(matrix[0])
prefix = [[0]*(cols+1) for _ in range(rows+1)]
for i in range(1, rows+1):
    for j in range(1, cols+1):
        prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + matrix[i-1][j-1]

4. 前缀和与其他优化技术的结合

前缀和可以与其他优化技术强强联合，产生更强大的效果：

4.1 前缀和+二分查找

在洛谷P1281问题中，还可以使用二分答案法：二分搜索可能的最大页数，用前缀和快速验证是否可行。

def is_possible(x):
    segments = 1
    current_sum = 0
    for num in pages:
        if current_sum + num > x:
            segments += 1
            current_sum = num
            if segments > k or num > x:
                return False
        else:
            current_sum += num
    return segments <= k

这种方法时间复杂度为O(nlogS)，其中S是总页数，适合更大数据规模。

4.2 前缀和+单调队列

对于滑动窗口类问题，前缀和与单调队列结合可以优化到O(n)：

from collections import deque

def max_subarray(nums, k):
    prefix = [0]
    for num in nums:
        prefix.append(prefix[-1] + num)
    
    q = deque()
    q.append(0)
    max_sum = float('-inf')
    
    for i in range(1, len(prefix)):
        while q and prefix[i] - prefix[q[0]] > k:
            q.popleft()
        if q:
            max_sum = max(max_sum, prefix[i] - prefix[q[0]])
        while q and prefix[i] <= prefix[q[-1]]:
            q.pop()
        q.append(i)
    
    return max_sum

4.3 前缀和+哈希表

解决子数组和等于特定值的问题：

def subarray_sum(nums, target):
    prefix = {0: 1}
    current_sum = 0
    count = 0
    for num in nums:
        current_sum += num
        count += prefix.get(current_sum - target, 0)
        prefix[current_sum] = prefix.get(current_sum, 0) + 1
    return count