本专题【动态规划总结】将主要分为4个部分，主要参考leetcode用户（fun4leetcode）对该类问题的总结，并添加自己的个人理解所作。
问题抽象
问题描述
该类问题主要在于对小区间内的dp值进行求取，并将现有值加入，用于更新大区间的dp值，最终得出答案。该类题目的难度中等起步，难的可以出到非常难。
通用方法
通用模板中的遍历方式是基础中的基础，即求dp[i] ~ dp[j] (j - i = 0,1,2 ...n)的方法，一般求解该类题目必使用，在缺失信息时，通常需要补齐相应的其他信息，将dp维度升为三维。
for(int l = 1; l<n; l++) {
for(int i = 0; i<n-l; i++) {
int j = i+l;
for(int k = i; k<j; k++) {
dp[i][j] = max(dp[i][j], dp[i][k] + result[k] + dp[k+1][j]);
}
}
}
return dp[0][n-1]
示例题目
-
Minimum Cost Tree From Leaf Values
该问题是对示例代码的最好解释：难度中等 小技巧：求最小值时 最大值以Integer.MAX_VALUE表示 -
Unique Binary Search Trees
通用问题求解 -
Minimum Score Triangulation of Polygon
通用问题求解，但是难度比较高，难点在于对多边形dp的选取，以及由于多边形的终点和起点相连带来的困难
*tips*：对于多边形类的问题，需要记住选取一个点为起点，另外一个点作为终点。即‘多边形也有终点和起点’
-
Remove Boxes
难度极高。难点在于对丢失信息的处理：需要增加维度补充dp信息。另开一题详解。 -
Minimum Cost to Merge Stones
难度很高，难点在于K堆这个选项：1：如何判断n堆是否可合成为一堆？ 2：k = 2 和 k= 其他值是解法不同，如何分类？ 另开一题详解。
*tips*：解题时基本要遵循的原则：即难度较大的题目，一定可以分解为一个个可以被准确理解的小难题并逐个击破。
-
Burst Balloons
难度较大：但当时求解时已经找到问题的关键：即最后一个戳破的气球为缺失的信息，卡在了另外一个难点：将corner case转变为一般的问题，去处理戳气球时的边界问题。 -
Guess Number Higher or Lower II
难度一般：加入了二分法的思想处理大小比较问题。
总结
该类问题是动态规划过程的常规问题，主要难点在于区间和并过程中题目给出的各种条件限制带来的难度，必要时需要提高维度解答问题。