1 题目
1.1 题目所需求出内容
对于本题，最终要求：一个最小值
1.2 题目背景、允许、禁止与限制
背景：有一个长度为 nnn 的字符串 sss，其中有 kkk 种字符，每种字符都有相对应的添加或删除花费
允许：在字符串的任意位置添加或删除一个元素，最终使得整字符串成为回文串
禁止：
1.3 数据范围与猜测
限制：最终求最小花费
1≤n≤2000⟶O(n2)1 \le n \le 2000 \longrightarrow O(n^2)1≤n≤2000⟶O(n2)
1.4 一句话概括题意
有一个字符串，其中每种字符都有独特的删除和添加的花费，求将整个字符串变为回文串的最小花费
2 题目破题推导
> 注：以下七种方法都可以考虑一下
2.1 大拆小、小组大
2.2 正向思维转逆向思维，逆向思维转正向思维
2.3 分情况考虑
一个长度为 nnn 的回文串 sss 满足：对于所有 k(1≤k≤⌈n÷2⌉)k(1 \le k \le \lceil{n\div2}\rceil)k(1≤k≤⌈n÷2⌉)，sk=sn−k***_k=s_{n-k****k =sn−k+1
因此，对于一个区间 [i,j][i,j][i,j] 来说，如果 s[i]=s[j]s[i]=s[j]s[i]=s[j] 那么如果区间 [i+1,j−1][i+1,j-1][i+1,j−1] 是回文串，则整体是回文串，否则不是
如果对于一个区间 [i,j][i,j][i,j] 来说，如果 s[i]≠s[j]s[i] \neq s[j]s[i]=s[j]，则为了使它变成回文，有四种可能的选择
* 删掉左边的字符 sis_isi ，现在需要的是把区间 [i+1,j][i+1,j][i+1,j] 变为回文的最小花费
* 删掉右边的字符 sjs_jsj ，现在需要的是把区间 [i,j−1][i,j-1][i,j−1] 变为回文的最小花费
* 在左边增加一个字符 sjs_jsj ，现在需要的是把区间 [i,j−1][i,j-1][i,j−1] 变为回文的最小花费
* 在右边增加一个字符 sis_isi ，现在需要的是把区间 [i+1,j][i+1,j][i+1,j] 变为回文的最小花费
2.4 数学
2.5 以终为始、以始为终
2.6 手动推导
2.7 边界测试
3 模型匹配
> 格式为："关键词：...... ⟶\longrightarrow⟶ ......\huge{......}......"
关键词：区间，回文 ⟶\longrightarrow⟶ 区间动态规划\huge{区间动态规划}区间动态规划
4 最终代码（禁止抄袭，仅用于参考）
