1312. 讓字符串成為回文串的最少插入次數

給你一個字符串?s?，每一次操作你都可以在字符串的任意位置插入任意字符。

請你返回讓?s?成為回文串的?最少操作次數?。

「回文串」是正讀和反讀都相同的字符串。

思路：

本題要求的是最少插入次數，規定dp[i][j]是從i到j的最小插入次數，此時研究dp[i][j]的構成。

當i位置和j位置元素一致的時候，可以視為i+1，j-1范圍的元素兩邊各加一個相同的值，則插入字符次數一樣，因為可以看成在已經是回文的字串變成一個更長的字串。

當i位置和j位置不同時，此時可以分情況討論，dp[i][j]的可能構成是對（i，j-1）的回文序列加上j位置元素，則只需要再加一即可構成新的回文序列（所加的就是一個j位置的數值），同理，也可能是（i-1，j）的回文序列再加上i位置元素，此時也是加一，也可能是（i+1，j-1）位置的回文序列，在兩側分別加一個元素（一個加i位置，一個加j位置），則dp[i][j]就是上述三種情況的最小值。

初始化時每個元素自己一定是回文，故均是0開局即可。

最后返回的是（0到n-1）位置的最小切割次數，故返回dp[0][n-1]即可。

class Solution {
public:int minInsertions(string s) {int n=s.size();vector<vector<int>>dp(n,vector<int>(n,INT_MAX));for(int j=0;j<n;j++){for(int i=j;i>=0;i--){   int k=0;if(s[i]==s[j]){if(i+1<=j-1){k=dp[i+1][j-1];}}else{  if(i+1<=j-1){   k=min(dp[i+1][j-1]+2,min(dp[i+1][j]+1,dp[i][j-1]+1));}elsek=1;}dp[i][j]=min(k,dp[i][j]);}}return dp[0][n-1];}
};