啥也不用说，不会动态规划绝对看不懂，请不会动态规划的同志们先戳这里了解基础动态规划。
▎什么是区间动态规划？
区间动态规划可以理解为用了分治的动态规划。
顾名思义，动态规划中涉及了区间，那么这正好和分治常用题型一样，如果你知道分治是什么，那么就很容易理解了。
那么先来想想分治是什么？分而治之，就是把一个大问题分成小问题，再把小问题的结果合并起来，就得到了原大问题的结果。
掺了分治的动态规划也可以这样，比方说现在要求f[i][j]，那么我们总能找到k，使i≤k<j，分别求出f[i][k]和f[k+1][j]的值，再加起来，就是f[i][j]的值。图解一下就是这样的：
当要求的是最优值时就可以表示为f[i][j]=max{f[i][k]+f[k+1][j]}，其中k是变量，依次在区间[i,j]中找到k值，计算找到最大的f[i][k]+f[k+1][j]值，就是f[i][j]的值。
你可能会问怎么知道f[i][k]和f[k+1][j]的值，很简单，要么递归，要么递推，递归的话直到递归边界会返回一个值，逐步回带；递推是一步一步算上来的，在算f[i][j]以前就先算过了f[i][k]和f[k+1][j]。
▎实战演练
可能有点难理解，主要是却例子，那么就直接上题吧！
信息奥赛一本通1570能量项链题
☞『题目』
1570：【例 2】能量项链时间限制: 1000 ms 内存限制: 524288 KB
提交数: 279 通过数: 189 【题目描述】
原题来自：NOIP 2006
在 Mars 星球上，每个 Mars 人都随身佩带着一串能量项链。在项链上有 N 颗能量珠。能量珠是一颗有头标记和尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记必定等于后一颗珠子的头标记。因为只有这样，通过吸盘——Mars 人吸收能量的器官的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可被吸盘吸收的能量。如果一颗能量珠头标记为 m，尾标记为 r，后一颗能量珠头标记为 r，尾标记为 n，则聚合后释放出 m×r×n Mars单位的能量，新珠子头标记为 m，尾标记为 n。
当需要时，Mars 人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不一样的。请设计一个聚合顺序使得一串珠子聚合后释放出的总能量最大。
例如，设 N=4，四颗珠子头标记与尾标记分别为 (2,3),(3,5),(5,10),(10,2)。我们用记号 ⨂ 表示两颗珠子的聚合操作，(j⨂k) 表示 j,k两颗珠子聚合后释放出的能量，则4,1两颗珠子聚合后所释放的能量为(4⨂1)=10×2×3=60，这一串项链可以得到最优值的一个聚合顺序所释放出的总能量为(((4⨂1)⨂2)⨂3)=10×2×3+10×3×5+10×5×10=710