区间\(DP\)

题目清单：

状态设计

\(1.\)对于这一类问题，一般设计状态为\(dp[i][j]\)，表示完成\(i-j\)区间的答案。
\(2.\)有一些奇葩的情况，可以这样设计状态：\(dp[i][j]\)表示完成\(j\)时，左端点为\(i\)，右端点为\(j-1\)

状态转移

思想是用已经更新的小区间扩展到未被更新的大区间，关键在于如何更新，如何扩展
一种办法是枚举断点把一个大区间划分成小区间
另一种办法是奇葩的倍增思想传送门

有三种\(DP\)顺序
\(1.\)先枚举区间长度，再枚举左端点，再枚举断点，因为区间长度从小到大，所以子状态一定都被更新，切忌先枚举左端点。
\(2.\)倒序枚举，即左端点(\(i\))\(n->1\)，右端点(\(j\))\(i->n\)，断点\(i-->j\)。
\(3.\)记忆化搜索，这样做无需考虑枚举顺序
\(4.\)倍增思想，\(dp[i-1][dp[i-1][j]]\)，见上面链接

需要注意几点：
\(1.\)注意初始化区间长度为\(1\)时的\(DP\)值
\(2.\)对于环应该先将它断开变成两倍长的链再区间\(DP\)，最后对于所有\(dp[i][i+n]\)取答案
\(3.\)有时候最优答案不一定会出现在\(dp[1][n]\)，需要对于\(DP\)过程中每一个值取最优值。

CSP2019算法总结---DP

原文：https://www.cnblogs.com/Liuz8848/p/11718615.html