算法导论——区间DP

今天我来**浅谈一下区间DP**。 常见的区间DP**有一定的范围**，例如$f[i][j]$表示**从i到j的最长上升子序列的长度**。 这里，由于这个值**是唯一的**，所以可以这么记录。 那么一般的区间DP的**动态转移方程**是怎样的呢？ 其实这个并不固定，需要**视题目而定**，毕竟**随机应变才是真本事**。 一般的**区间DP的循环**与常规DP不同，大致是这样： ```cpp for(int k=0;k<=n-1;k++) for(int i=1;i<=n-k;i++) int j=i+k; ... ``` 这段代码的重点在于枚举的是**区间长度和区间起点**。 有同学可能会问了：**为什么要这么枚举呢？** 可以这么理解：当$k=0$时，$i=1-n$，而当$k=n-1$时，$i=1$，当$k=\frac{n}{2}$时， $i=\frac{n}{2} -n$，也就是说这段代码的时间复杂度为$O\left(\frac{n^2}{2}\right)$。 不过，其实你**如何枚举都是这个时间复杂度**，所以完全可以根据自己的喜好、习惯来写。 其实我还**没有说什么就已经写了一大段了**，所以说这只是浅谈而已，**不过，放心好了，我以后还会更新的**，就到这里吧