Interval DP
区间类动态规划的明显特点就是在一段范围内找一个最大或最小值，或者最长什么的，另外一个明显特点就是一般是利用输入数据的长度建立一个n * n的矩阵，利用此矩阵中的下标来表示这个输入数据区间中的信息，这也意味着i > j的那部分矩阵是完全用不到的，同时也意味着如果用记忆化搜索来做这类题的话将无法优化空间复杂度（因为一半的矩阵空间实际上是用不到的），但是这类题一般情况下的记忆化搜索DP逻辑更加清晰，更容易实现，如果非要用矩阵递推实现的话，有一个明显的和坐标接龙类DP不同的地方就是DP的base case位置是所有i=j的位置，也就是矩阵的对角线处，而每次递推是平行于此对角线向右上角(dp[0][n - 1])推进的，这也导致循环的坐标不是特别好写，但是也还是能做的
区间类DP一个很重要的问题就是横纵坐标到底代表什么，依照现在做过的题来说总共见到过两种
- dp[i][j]表示i-j的范围的元素，这里i小于j，是一段真范围
- dp[i][j]表示长度为i的输入中长度为j的一个子范围的最优解，这里j小于i，这种表示方法在interleaving string和max expression value中见过