【学习笔记】区间dp

区间 dp 主要思想：

想求区间 $i$ ~ $j$ 的最优解，我们可以根据小区间的最优解，来得出大区间的最优解。具体就是枚举每一个中点，然后 $dp_{i,j}=max(dp_{i,j},dp_{i,k}+dp_{k+1,j}+num)$（num，取max和min 要根据题目要求来定）

环形问题解决方法：

开两倍（把数据复制到原来的后面），也就是对 $1$ ~ $2 \times n$ 进行动态规划，最后取 $dp_{1,n}$,$dp_{2,n+1}$ ......  的最优解。这样做是为了把环变成链。

注意：

• 初始化
• for 循环的正序和倒序。选择正序还是倒序背后的逻辑是“dp时大区间是根据小区间得到解的，这就要保证小区间都算过”。