网站建设方案书一定要交,企业网站的网址通常包括,淘宝网的公司注册名称,个人网站可以备案了吗动态规划
思路#xff1a; 通过插入字符构造回文串#xff0c;要想插入次数最少#xff0c;可以将字符串 s 的逆序 s 进行比较找出最长公共子序列#xff1b;可以先分析#xff0c;字符串 s 通过插入得到回文串 ps#xff0c;其中间的字符应该不会变化#xff1a; 若 s… 动态规划
思路 通过插入字符构造回文串要想插入次数最少可以将字符串 s 的逆序 s 进行比较找出最长公共子序列可以先分析字符串 s 通过插入得到回文串 ps其中间的字符应该不会变化 若 s 的长度为奇数那么它的回文中心为单个字符 c。例如当 s adgda 时它的回文中心为单个字符 g。我们可以断定回文中心 c 一定是原字符串 s 中的字符否则如果 c 是通过操作添加的字符那么我们可以舍弃这一步操作此时 s 成为长度为偶数的字符串并且它仍是回文串在例子中即 adgda - adda 若 s 的长度为偶数那么它的回文中心为两个字符 cc例如当 s adggda 时它的回文中心为两个字符 gg。我们同样可以断定回文中心 cc 一定是原字符串中的两个字符否则如果 cc 中有至少一个是通过操作添加的字符那么我们可以舍弃这些操作此时 s 成为长度为偶数舍弃一次操作或奇数舍弃两次操作的字符串并且它仍是回文串在例子中即 adggda - adgda 或 adggda - adda。 可以通过原字符串与逆序字符串进行“并集”构建回文字符串可以假设字符串 s 分成三部分 s(l) c s(r)则其逆序字符串 s(r) c s(l) 如果构建之后的回文字符串看作一块板子原串和逆串像两个“缺了孔”的两块板子叠在一起补上“缺的孔”就构成了回文串一样的是公共子串 那么需要补上的“孔”的个数为原串长度减去公共子串长度 综上问题回到求取两个字符串的最长公共子串参考 力扣1143. 最长公共子序列
class Solution {
public:int minInsertions(string s) {int n s.size();std::string invs(s.rbegin(), s.rend());std::vectorstd::vectorint dp(n 1, std::vectorint(n 1));for (int i 1; i n; i) {for (int j 1; j n; j) {dp[i][j] std::max(dp[i - 1][j], dp[i][j - 1]);if (s[i - 1] invs[j - 1]) {dp[i][j] std::max(dp[i][j], dp[i - 1][j - 1] 1);}}}return n - dp[n][n];}
};
————————————————————————————————————
