线性动态规划：最小插入次数构造回文串 题目描述 给定一个字符串s，你可以在任意位置插入任意字符，请计算最少需要插入多少次才能将s变成回文串。例如，对于字符串"ab"，插入1次变成"aba"或"bab"；对于字符串"abc"，插入2次变成"abcba"等。 解题思路 这个问题可以转化为：找到原字符串中最长的回文子序列，然后计算需要插入的字符数。因为最长的回文子序列不需要插入，只需要为不在这个子序列中的字符插入对应的对称字符即可。 解题步骤 定义状态 设dp[ i][ j ]表示字符串s从第i个字符到第j个字符（闭区间）的子串变成回文串所需的最小插入次数。 状态转移方程 当s[ i] = s[ j ]时： 两端的字符相同，它们可以自然形成对称，因此不需要为这两个字符额外插入。此时dp[ i][ j] = dp[ i+1][ j-1 ] 当s[ i] ≠ s[ j ]时： 两端的字符不同，我们需要选择两种操作之一： 在j后面插入一个与s[ i]相同的字符，这样s[ i]就能匹配新插入的字符，问题转化为dp[ i+1][ j ] 在i前面插入一个与s[ j]相同的字符，这样s[ j]就能匹配新插入的字符，问题转化为dp[ i][ j-1 ] 取这两种操作的最小值，并加上本次插入操作：dp[ i][ j] = min(dp[ i+1][ j], dp[ i][ j-1 ]) + 1 边界条件 当i = j时：单个字符本身就是回文，不需要插入，dp[ i][ j ] = 0 当i > j时：空字符串，dp[ i][ j ] = 0 计算顺序 由于dp[ i][ j]依赖于dp[ i+1][ j-1]、dp[ i+1][ j]和dp[ i][ j-1 ]，我们需要从较短的子串开始计算，逐步扩展到整个字符串。 具体计算过程 以字符串"abc"为例： 初始化单个字符： dp[ 0][ 0] = 0, dp[ 1][ 1] = 0, dp[ 2][ 2 ] = 0 计算长度为2的子串： 子串"ab"：s[ 0]≠s[ 1]，dp[ 0][ 1] = min(dp[ 1][ 1], dp[ 0][ 0 ]) + 1 = min(0,0) + 1 = 1 子串"bc"：s[ 1]≠s[ 2]，dp[ 1][ 2] = min(dp[ 2][ 2], dp[ 1][ 1 ]) + 1 = min(0,0) + 1 = 1 计算整个字符串"abc"： s[ 0]≠s[ 2]，dp[ 0][ 2] = min(dp[ 1][ 2], dp[ 0][ 1 ]) + 1 = min(1,1) + 1 = 2 因此，"abc"需要最少2次插入变成回文串。 算法优化 这个解法的时间复杂度是O(n²)，空间复杂度也是O(n²)。我们可以使用滚动数组将空间复杂度优化到O(n)。 总结 这个问题的核心思想是将最小插入次数问题转化为寻找最长回文子序列问题，通过动态规划自底向上地计算所有子问题，最终得到原问题的最优解。