题解 | #变回文串的最少插入次数#
变回文串的最少插入次数
http://www.nowcoder.com/practice/bae2652b4db04a438368238498e4c13e
动态规划 :初始化dp[i][i]=0， 从右下角开始比较i=n-2开始，第i个字符和其后的所有字符对比填充，若字符不相等，则dp[i][j]=min(dp[i][j-1],d[i+1][j])+1;若相等则dp[i][j]=d[i+1][j-1]。
n o w c o d e r
n 0 1 2 3 2 3 4 5 <-end
o 0 1 2 1 2 3 4
w 0 1 2 3 4 5
c 0 1 2 3 4
o 0 1 2 3
d 0 1 2
e 0 1<-start
r 0
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param str string字符串
* @return int整型
*/
int minInsert(string str) {
// write code here
int n=str.size();
int a[n][n];
for(int i=0;i<n;i++){
a[i][i]=0;
}
for(int i=n-2;i>=0;i--){
for(int j=i+1;j<n;j++){
if(str[i]==str[j]){
a[i][j]=a[i+1][j-1];
}
else a[i][j]=min(a[i+1][j],a[i][j-1])+1;
}
}
return a[0][n-1];
}
};
博世一面4人在聊