algorithm-dp-split

划分型dp

对数组或者字符串进行位置划分，划分成几个子数组或者子字符串

判定能否划分

一般定义f[i]表示长为i的前缀a[:i]能否划分，枚举最后一个子数组的左端点L，从f[L]转移到f[i]，并考虑a[L:j]是否满足要求

• 2369. 检查数组是否存在有效划分(1780)

计算划分最优值

定义f[i]表示对于前缀[0:i)所得到的最优解，枚举最后一个子数组的左端点L，从f[L]转移到f[i]，并考虑子数组[L:i)对最优解的影响

• 2707. 字符串中的额外字符(1736)
• 3538. 合并得到最小旅行时间：三维dp：区间[i,j]+剩余合并次数leftK（记忆化搜索写法）

约束划分个数

定义f[i][j]表示对于前缀[0:i)划分成j个连续子数组所得到的最优解，枚举最后一个子数组的左端点L，从f[L][j-1]转移到f[i][j]，并考虑子数组[L:i)对最优解的影响

• 2911. 得到 K 个半回文串的最少修改次数(2608)
• 3599. 划分数组得到最小 XOR：经典二维+枚举左端点，记忆化和递推两种写法

不相交区间

• 2008. 出租车的最大盈利(1872)