知周所众，\(DP\) 有一大堆杂七杂八的优化，例如线段树优化\(DP\)、斜率优化、单调队列优化等等等等一大坨。
本篇博客，就来讲一讲。
一般形式（可用范围）
对于和
当你的 \(DP\) 式子里有以下两种形式就可以使用。
形式1：
\[dp_i = \sum_{j=L_i}^{R_i} f(j) + val_i
\]
其中，\(f(j)\) 表示只和 \(j\) 有关的数， \(val_i\) 表示任意数
形式2：
\[dp_{i,j} = \sum_{k=L}^R dp_{i - 1, k}
\]
为什么这两种能用前缀和优化呢？
我们注意力惊人，一眼看出这里有重复的地方，想想前缀和的作用，可以发现前缀和足以优化掉最内层的一个循环。
对于最值
同上，只需要看要用前缀最值还是后缀最值。
例题
Distance Sequence
题目翻译：
有多少个长度为 \(N\) 的整数序列 \(A=(A_1,\ldots,A_N)\) 满足以下所有条件？
-
\(1\le A_i \le M\) \((1 \le i \le N)\)
-
\(|A_i - A_{i+1}| \geq K\) \((1 \le i \le N - 1)\)
由于计数可能很大，请对 \(998244353\) 求模。
做法
暴力做法
\(dp_{i,j}\) 表示