664. 奇怪的打印机

1682. 最长回文子序列 II(plus会员)

1690. 石子游戏 VII 1745. 回文串分割 IV

1000. 合并石头的最低成本

664. 奇怪的打印机

1. 确定dp数组含义和下标：dp[i][j] 为 [i, j] 区间的最小打印次数
2. 递推公式：对于区间，可以从边界开始考虑
3. 当s[i] == s[j]时，打印 s[i] 时顺便就可以打印 s[j]，中间的区域是可以被覆盖的，所以只考虑边界，只需

要打印一次 i 位置，j 位置也被顺便打印完成，即等于 j 位置不计算的次数，所以 dp[i][j] = dp[i][j - 1]

1. 当s[i] != s[j]时，可以分为两个区间，[i, k]和[k + 1, j]， k 取 [i, j)，此时只要找到两个区间d打印次数之和

最小的次数即可，即 dp[i][j] = min(dp[i][k] + dp[k + 1][j])

1. 初始化：考虑到区间长度为1，即 i == j 时，dp[i][i] = 1
2. 遍历顺序：i 从大到小，j 从小到大，因为在 s[i] != s[j] 的情况下，dp[i][j] 依赖于 dp[i][k], dp[k + 1][j]
3. 如果 i 从 0 开始，k 从 i 开始，那么对于dp[k + 1][j]，左边界取的是 i + 1，此时可能就没有被遍历过
4. 如果 i 从 n - 1 开始，k 从 i 开始，那么对于dp[k +1][j]，左边界取的是 i + 1，此时 i 是倒序遍历，所以

dp[k + 1][j] 肯定被遍历过了

1. j 同理，只有从 i + 1开始，k 从 i 开始，dp[i][k]才会被遍历过，保证无后效性

BFS

一些实现细节：

1. 是否访问的标识一定要处理好，不然就炸了
2. 根据题意，选择使用邻接矩阵、邻接表存储图（偏向邻接表）
3. 和背包模型一样，要学会抽象