区间型
区间型
给定一个序列/字符串，进行一些操作
最后一步会将序列字符串去头/去尾
剩下的会是一个区间[i, j]
特点：
题目会存在Subarray/Substring相关的字眼
状态：
f[i][j]表示子串[i,j]时的性质，或f[i][k]表示以i开头长度为k的区间性质
用f[i][j]表示数组/字符串中[i,j]这一段区间的最优值/可行性/方案总数
题目特点：
题目会存在Subarray/Substring相关的字眼
大区间依赖小区间，循环方式不同
因此要从较小区间计算到较大的区间
转移：
大的 Subarray/Substring 的依懒于小的Subarray/Substringdp[i][j]=max/min/sum/or([i,j]之内更小的若干区间])
有的问题，需要第三重循环，枚举区间断点
子串问题，无需第三重循环，只需要判断两侧即可
解决方案：
- i 倒着循环，j 正着循环
- 先循环区间长度，加再循环区间起点
端点类
判断回文子串
状态：dp[i][j] 表示 i,j 这一段是不是回文串
转移：dp[i][j]=dp[i + 1][j - 1] and s[i] == s[j]
边界：dp[i][i]=true, dp[i][i + 1] == (s[i] == s[i + 1])
答案：dp[x][y]对于任意想要检测是否是回文串的下标范围 x-y
LPS 最长回文子串（substring需要连续）
状态：f[i][j]表示 i,j 这一段是回文串
转移：f[i][j]=f[i+1][j-1]&&S[i]==[j]
边界：f[i][i]=true, f[i][i+1]=(s[i] == s[i + 1])
答案：更新时最长的段
LPS 最长回文子序
状态：f[i][j]表示 i,j 这一段的最长回文子序列的长度
转移：f[i][j]=max{f[i+1][j], f[i][j-1], f[i+1][j-1]+2|S[i]==[j]}
边界：f[i][i]=1
答案：f[0][n-1]
按照区间长度j-i从小到大的顺序去算
加找最优解，加pi[i][j]数组，记录这个位置做的选择，0:干嘛，1:干嘛，3:干嘛
断点类
On3 Floyd
石子归并游戏
每次合并2堆，本次合并的费用是这一堆重量的综合
状态：f[i][j]表示合并i到j的最小花费
转移：f[i][j]=min{f[i][k] + f[k+1][j]}+sum(i,j), i<=k<j
边界：f[i][i]=0
答案：f[0][n-1]
合并石头的最低成本
一条直线上有 N 堆石头，每次可以合并连续的 K 堆石头，代价是 K 堆石头之和，问最终需要合并成一堆的最小代价之和,lc1000
状态：f[i][j][k]表示i到j这一段合并为k堆石子的最小代价
转移：f[i][j][k]=min{f[i][x][k-1]+f[x][j][1]}+sum(i,j)
答案：f[0][n-1][1]
状态优化：
状态：f[i][j]表示i到j合并到不能合并的最小花费
转移：f[i][j]=min[m,i,j-1,k-1]{f[i][m]+f[m+1][j]}+sum(i,j)|(j-i)%(k-1)==0
答案：f[0][n-1]
四边形优化
Burst Balloons 爆气球
需要在数组前后各加1
状态：dp[i][j]表示戳爆 i和j之间所有气球之后(含i,j)的最大积分
转移：dp[i][j] = max{dp[i][k-1] + dp[k+1][j] + nums[i-1] * nums[k] * nums[j+1]} i<=k<=j
边界：
答案：dp[0][n-1]
特殊定义：（不推荐，临场发挥容易失误）
状态：dp[i][j]表示戳爆 i和j之间所有气球之后(不含i,j)的最大积分
转移：dp[i][j] = max{dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]} i<k<j
答案：dp[0][n-1]
切棍子的最小成本
状态：dp[i][j]表示戳爆 i和j之间所有气球之后(含i,j)的最大积分
转移：dp[i][j] = min{dp[i][k-1] + dp[k+1][j]} + nums[j+1] - nums[i-1]} i<k<j
边界：
矩阵乘法的最小花费
状态：f[i][j]表示i到j连乘的最小花费
转移：f[i][j]=min{f[i][k]+f[k+1][j]+pqr}
边界：f[i][i]=0
矩阵乘法的方案数
状态：f[i][j]表示i到j连乘的方案数
转移：f[i][j]=sum{f[i][k]*f[k+1][j]}
边界：f[i][i]=1
双区间
扰乱字符串 Scramble String
这里所有串都是S和T的子串，且长度一样
所以每个串都可以用（起始位置，长度）表示
状态：f[i][j][k]表示S1能否通过变换成为T1
- S1为S从字符i开始的长度为k的子串
- T1为T从字符j开始的长度为k的子串
转移：f[i][j][k]=or{f[i][j][w]&&f[i+w][j+w][k-w] or f[i][j+k-w][w]&&f[i+w][j][k-w]}
边界：f[i][j][1]=s[i]==s[j]
答案：f[0][0][n]
空间复杂度为record数组，长度为n； 每个子数组record[i]最多不超过i（组合数）*i（每个字符串长度）个字符； 求和(12+22+...+n^2=>O(n3)), 故空间复杂度的上限为O(n3)