2026-02-24
1 前缀和优化DP
1.1 核心思想
用空间换时间
通过预处理前缀和数组，将求和操作转化为前缀和数组的两次访问（相减）。
1.2 常见可优化类型
1.2.1 一维DP：区间求和
状态定义：
\(dp[i]\) 表示考虑前 \(i\) 个元素或以 \(i\) 结尾的答案转移方程：
\[dp[i] = \sum_{j = L[i]}^{R[i]} g(j) + C[i]$ \]优化：
预处理 \(g(j)\) 的前缀和
\[sum[j] = \sum_{x=0}^{j} g(x) \]则 \(dp[i] = sum[R[i]] - sum[L[i]-1] + C[i]\)
1.2.2 二维DP：由上一层的连续区间转移
状态定义：
\(dp[i][j]\) 表示处理完前 \(i\) 个物品，当前状态为 \(j\) 的答案
转移方程形式：
\[dp[i][j] = \sum_{k = L}^{R} dp[i-1][k] \]优化：
在计算第 \(i\) 层之前，先预处理出第 \(i-1\) 层状态的前缀和
\[sum[i-1][k] = \sum_{x=0}^{k} dp[i-1][x] \]则 \(dp[i][j] = sum[i-1][R] - sum[i-1][L-1]\)
1.2 习题讲解
1.2.1 跳跃游戏 (Jump Game)
链接 ： 暂无
1.2.1.1 暴力DP思路
状态定义：
\(dp[i]\) 表示是否能到达站点 \(i\)
转移方程：
\(dp[i] = true\)，如果存在一个 \(j\) 满足 \(j\) 可到达，\(S[j]=='0'\)，且 \(i\) 在 \(j\) 的跳跃范围内
1.2.1.2 前缀和优化分析
观察：
对于不同的 \(i\):
\(dp[i]\) 的值总是由上一段连续区间内的 \(dp\) 值之和决定
优化方法：
维护一个前缀和数组 \(preSum\)\[preSum[i] = \sum_{x=0}^{i} dp[x] \]那么，\(dp[i]\) 所需区间的和可以 \(O(1)\) 计算：
\(区间和 = preSum[i - minJump] - preSum[max(0, i - maxJump) - 1]\) 注意处理边界
这样就将
1D/1D的DP优化为了1D/0D
1.2.2 Candies
链接 ： AtCoder： DP_M - Candies
1.2.2.1 暴力DP思路
状态定义：
\(dp[i][j]\) 表示分配到第 \(i\) 个孩子，已经分掉了 \(j\) 颗糖的方案数。
转移方程：
第 \(i\) 个孩子拿 \(k\) 颗糖，则前 \(i-1\) 个孩子分掉了 \(j-k\) 颗糖\[dp[i][j] = \sum_{k = max(0, j-a_i)}^{j} dp[i-1][j-k] \]复杂度：
\(O(N * K^2)\)，会超时
1.2.2.2 前缀和优化分析
观察：
\(dp[i][j]\) 的值由第 \(i-1\) 层状态的 一段连续区间 \([max(0, j-a_i), j]\) 的和决定
优化方法：
在计算第 \(i\) 行之前，预处理第 \(i-1\) 行的前缀和数组 \(sum_prev\)：
\[sum_{prev}[x] = \sum_{t=0}^{x} dp[i-1][t] \]那么转移变为：
\(dp[i][j] = sum_{prev}[j] - sum_{prev}[max(0, j-a_i) - 1]\)
注意边界，当下标为-1时，值为0
复杂度降为 \(O(N * K)\)
草稿
1.2.3 逆序对数列
链接 ： Luogu： P2513 [HAOI2009] 逆序对数列
1.2.3.1 填表法DP思路
状态定义：dp[i][j] 表示用前 i 个数（即1..i）组成的排列，逆序对数为 j 的方案数。
转移方程（考虑第 i 个数（最大数）的插入位置）：
插入到最后一个位置，新增0个逆序对；插入到倒数第二个，新增1个逆序对；...；插入到第一个，新增 i-1 个逆序对。
dp[i][j] = sum_{k=0}^{min(j, i-1)} dp[i-1][j-k]，等价于 dp[i][j] = sum_{t = max(0, j-(i-1))}^{j} dp[i-1][t]。
1.2.3.2 前缀和优化分析
观察：与Candies问题惊人地相似！dp[i][j] 仍然是由第 i-1 层的一段连续区间求和得到，区间的长度受 i-1 限制。
优化方法：
同样，预处理第 i-1 层的前缀和 sum[t] = sum_{x=0}^{t} dp[i-1][x]。
则转移可优化为：
dp[i][j] = sum[j] - (j-i >= 0 ? sum[j-i] : 0)。
复杂度从 O(n^2 * k) 降为 O(n * k)。
1.2.4 ABC253E Distance Sequence
1.2.4.1 暴力DP思路
状态定义：dp[i][j] 表示第 i 个数字为 j 的方案数。
转移方程：
dp[i][j] = sum_{l=1}^{j-K} dp[i-1][l] + sum_{l=j+K}^{M} dp[i-1][l]。 (需考虑 K=0 的特殊情况)
1.2.4.2 前缀和优化分析
观察：这次需要求的是第 i-1 层状态的两段不连续区间的和。但这两段区间本身仍然是连续的。
优化方法：
预处理第 i-1 层的前缀和 sum[x] = sum_{t=1}^{x} dp[i-1][t]。
则转移可优化为：
左区间和 = sum[max(0, j-K)] (注意下标从1开始)
右区间和 = sum[M] - sum[min(M, j+K-1)]
dp[i][j] = 左区间和 + 右区间和 (记得取模)。
复杂度从 O(N * M^2) 降为 O(N * M)。