动态规划在最少插入次数下构建回文串

以最小插入次数构造回文串

题目描述

当输入字符串s为"abcea"时, 该算法会返回数值2, 因为可以通过向字符串s中添加两个字符从而形成一个回文串（例如生成"abeceba"或"aebcbea"). 如果输入字符串s已经是回文（如s等于"aba"）, 那么该算法会返回数值0, 表示无需添加任何字符即可实现目标.

解题思路

base case：当变量i等于变量j时（即i=j），dp[i][j]=0；这是因为当i=j时字符串s[i...j]仅包含一个字符（即单个字符本身就是回文），因此无需进行任何插入操作。

如果s[i]与s[j]不同，则增加两个字符后必定能让区间[s[i], s[j]]成为一个回文字符串；然而，并不一定需要最少次数。

则：

1. 做选择，先将s[i...j-1]或者s[i+1...j]变成回文串
2. 根据1的选择，将s[i...j]变成回文

    //状态转移方程：
    if(s[i] == s[j]){
    	dp[i][j] = dp[i + 1] [j - 1];
    }else{
    	dp[i][j] = min(dp[i+1][j],dp[i][j - 1]) + 1;
    }

    int minInsertions(Str