划分型
划分型
划分型动态规划，属于序列型动态规划，但是通常需要加上段数信息
给定长度为N的序列或字符串，要求划分为若干段（有限段、不限段）
让你将字符串、数组划分为若干部分或指定个数部分
开动规数组时，n和k都需要+1
方程推导是去找最后一个部分从哪儿切开
要求将一个序列或字符串划分成若干满足要求的片段
解决方法：最后一步→最后一段，枚举最后一段的起点
不定段数，用
f[i]表示前i个元素分段后的可行性/最优值/方式数：- Perfect Squares, Palindrome Partition lI
指定段数，用
f[i][j]表示前i个元素分成j段后的可行性/最优值/方式数：- Copy Books
Palindrome Partitioning II
最小值
状态：f[i]表示前i可以被分成几个Palin
转移：f[i]=min{f[j]+1|isPalin[j][i-1]}
边界：f[0]=0
Palindrome Partitioning III
最小值
状态：f[i][k]表示前i被分成k个Palin的最小代价
转移：f[i][k]=min{f[j][k-1]+cost[j-1][i-1]}
边界：f[i][k]=Inf,f[i][1]=cost[0][i-1]
Copy Books 复印书籍问题
最小值：所有段的最大值最小（二分法也可以解答）
状态：f[k][i]表示前k个抄字员最少需要多少时间抄完前i本书
转移：f[k][i]=minj{max{f[k-1][j]+1|isPalin[j][i-1]}
转移：f[k][i]=min[0,i)j{max{f[k-1][j],sum[j,i-1]k{pages[k]}}
边界：f[i][0]=0, f[i][j]=Inf
On2k
可以用四边形不等式优化到Onk
Perfect Squares
最小值
状态：f[i]表示i可以被分成几个完全平方数之和
转移：f[i]=1+min{f[i-j2]}, j2[1,i]
边界：f[0]=0
单词划分
可行性
状态：f[i]表示前i个字符是否可以划分为符合要求的单词
转移：f[i]=or{dp[j] && isWord(j+1, i)}, j in [0,i]
Decode Ways
方案数
状态：f[i]表示前i个字符是否可以方案数
转移：f[i]=f[i-1]|ok(i)+f[i-2]|ok(i-1, i)
后缀优化
从i-1开始枚举i，然后求后缀和、或者统计之类的，来累计从[j,i-1)这段
j从i-1往0枚举，然后记录字符的频率，判断是否是平衡子串
状态：f[i]表示前i个字符最小划分数量
转移：f[i]=min{f[j]+1,[j,i-1] is balanced}
最小值：分割成m段的最大值最小
状态：f[i][j]表示前i个字符划分成j段的最大值
转移：f[i][j]=max{f[k][j-1]+sufSum}
边界：f[i][j]=Inf,f[0][0]=0