区间 DP

来源：基础算法精讲 by 灵茶山艾府

视频精讲：区间 DP

题意与示例

516. 最长回文子序列

题目链接：求字符串中最长回文子序列的长度。

示例：输入 s = "bbbab"，输出 4。

1039. 多边形三角剖分的最低得分

题目链接：把带权凸多边形剖分成三角形，求各三角形顶点乘积之和的最小值。

示例：输入 values = [1,2,3]，输出 6。

3472. 至多 K 次操作后的最长回文子序列

题目链接：最多执行 k 次字母循环相邻替换，求可得到的最长回文子序列长度。

示例：输入 s = "abced", k = 2，输出 3。

3040. 相同分数的最大操作数目 II

题目链接：每次删除首部两个、尾部两个或首尾元素，求所有删除和相同时最多能操作几次。

示例：输入 nums = [3,2,1,2,3,4]，输出 3。

1771. 由子序列构造的最长回文串的长度

题目链接：分别从两个单词选非空子序列并拼接，求能形成的最长回文串长度。

示例：输入 word1 = "cacb", word2 = "cbba"，输出 5。

1547. 切棍子的最小成本

题目链接：每次切割成本等于当前木棍长度，求完成所有指定切割的最小总成本。

示例：输入 n = 7, cuts = [1,3,4,5]，输出 16。