1️⃣题目描述
给你一个字符串 s
,每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s
成为回文串的 最少操作次数 。
「回文串」是正读和反读都相同的字符串。
示例1:
示例2:
示例3:
注意:
1 <= s.length <= 500
s 中所有字符都是小写字母。
2️⃣题目解析
状态表示:
dp[i][j]
:表示区间[i,j]字符串称为回文串的最少插入次数。
返回值:
dp[0][n-1]
3️⃣解题代码
class Solution {
public:
int minInsertions(string s) {
int n = s.size();
vector<vector<int>> dp(n,vector<int>(n));
for(int i = n - 1;i >= 0;i--)
{
for(int j = i + 1;j < n;j++)
{
if(s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1];
else dp[i][j] = min(1 + dp[i][j - 1],1 + dp[i + 1][j]);
}
}
return dp[0][n - 1];
}
};
最后就顺利通过啦!!!