【动态规划】C++解决回文串类算法题（最长/回文子串、分割回文串、回文子序列、最少插入次数） |
您所在的位置：网站首页 › 最长回文子字符串 › 【动态规划】C++解决回文串类算法题（最长/回文子串、分割回文串、回文子序列、最少插入次数） |
【动态规划】C++解决回文串类算法题（最长/回文子串、分割回文串、回文子序列、最少插入次数）
|
1. 前言
关于 动态规划的理解 与例题，点击👇 【动态规划】C++解决斐波那契模型题目（三步问题、爬楼梯、解码方法…） 有了上面的经验，我们来解下面 回文串类问题 2. 算法题 2.1_回文子串
思路 设置状态表示 dp[i][j]：字符串s->(i, j) 范围内的子串是否回文 写状态转移方程
代码 class Solution { public: int countSubstrings(string s) { int n = s.size(); vector dp(n, vector(n, false)); // dp[i][j]: s中{i, j} 范围的子串是否为回文串 // if(s[i] != s[j]) dp[i][j] = false; // 默认为false // 从下向上 + 从左向右 填表 int ret = 0; // 记录回文串个数 for(int i = n - 1; i >= 0; --i) { for(int j = i; j public: string longestPalindrome(string s) { // 动态规划： int n = s.size(); vector dp(n, vector(n, false)); string ret = ""; for(int i = n-1; i >= 0; --i) { for(int j = i; j public: bool checkPartitioning(string s) { int n = s.size(); // 预处理dp数组，用于判断{i, j}范围子串是否为回文串 vector dp(n, vector(n, false)); for(int i = n-1; i >= 0; --i) for(int j = i; j public: int minCut(string s) { int n = s.size(); // 预处理dp数组，用于判断{i,j}范围的最长子串是否为回文串 vector isPal(n, vector(n, false)); for(int i = n-1; i >= 0; --i) for(int j = i; j for(int j = 1; j int n = s.size(); // 初始化dp数组 vector dp(n, vector(n, 0)); // 填表 for(int i = n-1; i >= 0; --i) { dp[i][i] = 1; // i==j 即回文子序列长度为1时 for(int j = i+1; j public: int minInsertions(string s) { int n = s.size(); // 初始化dp数组: dp[i][j]表示 范围在{i, j}内的最少插入次数 vector dp(n, vector(n, 0)); // 填表 for(int i = n-1; i >= 0; --i) // 从下到上 for(int j = i + 1; j |
题意分析
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |