网站群建设,手表网站排名前十,上海网站排名优化怎么做,南宁手机网站设计策划作者推荐
【动态规划】【字符串】【表达式】2019. 解出数学表达式的学生分数
本文涉及知识点
动态规划汇总 记忆化搜索 回文 字符串
LeetCode1312. 让字符串成为回文串的最少插入次数
给你一个字符串 s #xff0c;每一次操作你都可以在字符串的任意位置插入任意字符。 请…作者推荐
【动态规划】【字符串】【表达式】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[left1][r-1] s[left]s[r] \\ dp[left1][r]1 \\ dp[left][r-1]1 \\ \end{cases} dp[left][r]min⎩ ⎨ ⎧dp[left1][r−1]dp[left1][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();vectorvectorint dp(n, vectorint(n, -1));return Cal(dp,s,0, n - 1);}int Cal (vectorvectorint 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);};
};测试用例
templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT 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(); vectorvector dp(c1, 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][i1]); 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]; };
扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
