作者推荐
【动态规划】【字符串】【表达式】2019. 解出数学表达式的学生分数
本文涉及知识点
记忆化搜索 回文 字符串
LeetCode1312. 让字符串成为回文串的最少插入次数
给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。
「回文串」是正读和反读都相同的字符串。
示例 1：
输入：s = “zzazz”
输出：0
解释：字符串 “zzazz” 已经是回文串了，所以不需要做任何插入操作。
示例 2：
输入：s = “mbadm”
输出：2
解释：字符串可变为 “mbdadbm” 或者 “mdbabdm” 。
示例 3：
输入：s = “leetcode”
输出：5
解释：插入 5 个字符后字符串变为 “leetcodocteel” 。
提示：
1 <= s.length <= 500
s 中所有字符都是小写字母。
动态规划
动态规划的状态表示
dp[left][r] 表示s[left,r]变成回文需要插入的字符数。
动态规划的转移方程
d p [ l e f t ] [ r ] = m i n { d p [ l e f t + 1 ] [ r − 1 ] s [ l e f t ] = = s [ r ] d p [ l e f t + 1 ] [ r ] + 1 d p [ l e f t ] [ r − 1 ] + 1 dp[left][r]=min\begin{cases} dp[left+1][r-1] & s[left]==s[r] \\ dp[left+1][r]+1 & \\ dp[left][r-1]+1 & \\ \end{cases}dp[left][r]=min⎩⎨⎧dp[left+1][r−1]dp[left+1][r]+1dp[left][r−1]+1s[left]==s[r]
用Cal函数代替dp向量：一，方便记忆。二，方便处理left > r。
动态规划的初始值
全为-1，表示未处理。
动态规划的填表顺序
递归计算dp[0][n-1]
动态规划的返回值
dp[0][n-1]
代码
核心代码
class Solution { public: int minInsertions(string s) { const int n = s.length(); vector<vector<int>> dp(n, vector<int>(n, -1)); return Cal(dp,s,0, n - 1); } int Cal (vector<vector<int>>& dp ,const string& s,int left, int r) { if (left > r) { return 0; } if (-1 != dp[left][r]) { return dp[left][r]; } if (s[left] == s[r]) { return dp[left][r] = Cal(dp,s,left + 1, r - 1); } return dp[left][r] = min(Cal(dp, s, left + 1, r) + 1, Cal(dp, s, left, r - 1) + 1); }; };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { string s; { Solution sln; s = "zzazz"; auto res = sln.minInsertions(s); Assert(0, res); } { Solution sln; s = "mbadm"; auto res = sln.minInsertions(s); Assert(2, res); } { Solution sln; s = "leetcode"; auto res = sln.minInsertions(s); Assert(5, res); } }
2023年2月第一版
class Solution {
public:
int minInsertions(string s) {
return s.length() - MaxNum(s);
}
int MaxNum(string s)
{
int c = s.length();
vector<vector> dp(c+1, vector©);
for (int j = 0; j < c; j++)
{
dp[1][j] = 1;
}
for (int len = 2; len <= c; len++)
{
for (int i = 0; i + len <= c; i++)
{
dp[len][i] = max(dp[len-1][i] ,dp[len-1][i+1]);
if (s[i] == s[i + len - 1])
{
dp[len][i] = max(dp[len][i], 2 + dp[len - 2][i + 1]);
}
}
}
return dp[c][0];
}
};
2023年2月 第二版
class Solution {
public:
int minInsertions(string s) {
string strInv(s.rbegin(), s.rend());
return s.length() - longestCommonSubsequence(s, strInv);
}
int longestCommonSubsequence(string text1, string text2) {
vector pre(text1.size()+1);
for (int i = 1; i <= text2.length(); i++)
{
vector dp(text1.size() + 1);
for (int j = 1; j <= text1.size();j++ )
{
dp[j] = max(pre[j], dp[j - 1]);
if (text2[i - 1] == text1[j - 1])
{
dp[j] = max(dp[j], pre[j - 1]+1);
}
}
pre.swap(dp);
}
return pre.back();
}
};
2023年7月版
class Solution {
public:
int minInsertions(string s) {
for (int i = 0; i <= s.length(); i++)
{
for (int j = 0; j <= s.length(); j++)
{
m_result[i][j] = -1;
}
}
return minInsertions(s, 0, s.length());
}
//左闭右开
int minInsertions(const string& s, int left, int r)
{
if (r - left <= 1)
{
return 0;
}
int& result = m_result[left][r];
if (-1 != result)
{
return result;
}
if (s[left] == s[r - 1])
{
return result =minInsertions(s, left + 1, r - 1);
}
return result = 1 + min(minInsertions(s, left + 1, r), minInsertions(s, left, r - 1));
}
int m_result[501][501];
};
