题解 | #变回文串的最少插入次数#

区间动态规划：

按照区间dp的步骤来

1. 确定状态：dp[i][j]表示从i-j的字串变成回文串的最少插入次数，所以，i-j的字串一定是回文串。
2. 划分阶段：区间长度
3. 决策选择：原问题与子问题之间的关系是

若str[i] == str[j]，则dp[i][j]的状态就是i+1~j-1的状态。 直接dp[i][j] = dp[i+1][j-1];

若str[i] != str[j]，则dp[i][j]的状态是i+1~j的状态下再插入一个字符(+1)

或者i~j-1的状态下再插入一个字符(+1)。

4. 初始条件：所有单个字符自己就是回文串，初始化为0；

5. 求解目标：dp[1][n]，也就是从第一个字符到最后一个字符的子串的状态

遍历方式：从状态转移可以看出，会从dp[i+1][j-1],dp[i+1][j],dp[i][j-1]三个方向转移，

即： i-1,j-1 i-1,j i-1,j+1

i,j-1 i,j i,j+1

i+1,j-1 i+1,j i+1,j+1

所以，应该从右下角遍历至左上角，才能在推导dp[i][j]时，上一个状态都是已知的。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return int整型
     */
    int minInsert(string str) {
        // write code here
        int n = str.size();
        vector<vector<int>> dp(n+1,vector<int>(n+1,0));
        for(int d = 2;d<=n;d++)
        {
            for(int i=n-d+1;i>=1;i--)
            {
                int j = i+d-1;
                if(str[i-1]==str[j-1])
                {
                    dp[i][j] = dp[i+1][j-1];
                }
                else {
                    dp[i][j] = min(dp[i+1][j],dp[i][j-1])+1;
                }
            }
        }
        return dp[1][n];
    }
};