第一类：

给出⼀个序列，明确要求分割成K个连续区间，要求我们计算这些区间的某个最有性质

题目813：将数组nums 分成 最多k个非空子数组，使得数组平均值的总和最大。

思路：

dp[i][j]：数组nums[:i+1] 切 j-1刀得到的最大平均值总和。初始化为负无穷。

递推公式：dp[i][j] = max(dp[i][j], dp[l][j - 1] + (sub_sums[i+1] - sub_sums[l+1])/(i-l))，dp[i][j]由少切一刀的dp[l][j - 1]和区间nums[l+1:i+1]共同决定。

遍历顺序：数组结尾 i 外层循环。刀j内层。多一刀的分割点 l [j-1, i-1]。正序遍历。 

题目1278：给定字符串s和整数k。把s分割成k个子串，每个子串都是回文。（可以修改部分字符）返回最少的修改数。

思路：

dp[i][j]：字符串s[:i+1] 切 j-1刀得到回文子串的最少修改数。初始化为正无穷。

递推公式：dp[i][j] = min(dp[i][j], dp[l][j-1] + self.to_pld(s[l:i]))，dp[i][j]由少切一刀的dp[l][j - 1]和区间 s[l:i]共同决定。

遍历顺序：数组结尾 i 外层循环。刀j内层。多一刀的分割点 l [j, i]。正序遍历。 

题目410：给定一个非负整数数组 nums 和整数k ，将这个数组分成k 个非空的连续子数组。使得这子数组和的最大值最小。

思路：

dp[i][j]：数组 nums[:i+1] 切 j-1刀得到的子数组，数组和的最大值的最小值。初始化为正无穷。

递推公式：dp[i][j] = min(dp[i][j], max(dp[l][j-1], sub_sum[i] - sub_sum[l]))，dp[i][j]由少切一刀的dp[l][j - 1]和区间 s[l:i]共同决定。

遍历顺序：数组结尾 i 外层循环。刀j内层。多一刀的分割点 l [j, i]。正序遍历。 

题目1335：给定一个工作难度jobDifficulty和工作天数d，工作必须按顺序进行，且每天至少完成一项任务。制定一份d天的工作计划表，使得难度最小。工作计划的总难度是这d天的难度之和，而一天的工作难度是当天应该完成工作的最大难度。

思路：其实就是切成d个子数组，子数组最大值的和最小。

dp[i][j]：数组 jobDifficulty[:i+1] 切 j-1刀得到的子数组，数组最大值的和的最小值。初始化为正无穷。

递推公式：dp[i][j] = min(dp[i][j], dp[l][j-1] + max(jobDifficulty[l:i]))，dp[i][j]由少切一刀的dp[l][j - 1]和区间 jobDifficulty[l:i]共同决定。

遍历顺序：数组结尾 i 外层循环。刀j内层。多一刀的分割点 l [j, i]。正序遍历。 

第二类

题目664：奇怪的打印机：每次只能打印由 同一个字符 组成的序列。每次打印会覆盖掉原来已有的字符。计算打印机打印 s 需要的最少打印次数。

思路：

dp[i][j]：s[i: j+1]的最少打印次数。初始化为正无穷大。由于是从中间往两边拓展的，就先把对角线的元素填为1.

递推公式：如果 s[i] == s[j]，dp[i][j] = dp[i][j-1]；否则就要遍历 for k in range(i, j): dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])

遍历顺序：只要填上三角的元素，行从下往上，列从左往右。

题目1547：给定长度为 n 个单位的木棍和数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置。每次切割的成本都是当前要切割的棍子的长度，返回切棍子的 最小总成本 。

思路：dp[i][j]：木棍[i: j+1]的切割总成本。初始化为正无穷大。

递推公式：对于木棍内部[i: j+1]的每一个可能切割点k: dp[i][j] = min(dp[i][j], cuts[j]-cuts[i] + dp[i][l] + dp[l][j])。如果遍历后还是inf，就等于0

遍历顺序：只要填上三角的元素，行从下往上，列从左往右。

题目1690：有 n 块石子排成一排 stones 。两个玩家在其回合中，可以从行中 移除 最左边的石头或最右边的石头，并获得剩余石头值之 和 作为得分。请返回两个玩家 得分的差值 。

思路：dp[i][j]：面对stones[i:j+1]，先手玩家可以得到的最大得分差。初始化为0.

递推公式：先手玩家面临取左边还是取右边的抉择。dp[i][j] = max(sub_sum[j+1] - sub_sum[i+1] - dp[i+1][j], sub_sum[j] - sub_sum[i] - dp[i][j-1])

遍历顺序：只要填上三角的元素，行从下往上，列从左往右。

题目1745：给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。

思路：先做出回文子串的dp方阵。dp[i][j] 代表s[i:j+1]为回文子串。然后用遍历i, j 两个切割点，看能否分成三个回文子串。

题目1000：有 n 堆石头，第 i 堆中有stones[i]块石头。每次将相邻的 k 堆石头合并为一堆，成本为这 k 堆中石头的总数。返回把所有石头合并成一堆的最低成本。

思路：dp[i][j]：将 i 到 j 的石头堆合并的成本。初始化为inf，对于每个k堆连续石头，可以先合并。dp[i][i+k-1] = sub_sum[i+k] - sub_sum[i]

递推公式：对于for l in range(i+k-1, j, k-1): dp[i][j] = min(dp[i][j], dp[i][l] + dp[l+1][j])

遍历顺序：只要填上三角的元素，行从下往上，列从左往右。