做名片模板网站,网站内链怎么删除,如何进行网络销售,网站开发与规划就业前景前言
大家好#xff0c;我是jiantaoyab#xff0c;开始刷动态规划的回文串类型相关的题目
动态规划5个步骤 状态表示 #xff1a;dp数组中每一个下标对应值的含义是什么dp[i]表示什么状态转移方程#xff1a; dp[i] 等于什么1 和 2 是动态规划的核心步骤#xff0c;…前言
大家好我是jiantaoyab开始刷动态规划的回文串类型相关的题目
动态规划5个步骤 状态表示 dp数组中每一个下标对应值的含义是什么dp[i]表示什么状态转移方程 dp[i] 等于什么1 和 2 是动态规划的核心步骤第三步是初始化保证填表的时候不越界填表顺序为了保证填写当前状态的时候所需要的状态已经计算过返回值 回文子串 题目分析 代码
class Solution {
public:int countSubstrings(string s) {int n s.size();int ret 0;vectorvectorbool dp(n, vectorbool(n));for(int i n - 1; i 0; i--){for(int j i; j n; j) // i j{if(s[i] s[j]) dp[i][j] i 1 j ? dp[i 1][j - 1] : true;if(dp[i][j]) ret;}}return ret;}
};最长回文子串 代码
动态规划版本
class Solution {
public:string longestPalindrome(string s) {int n s.size();vectorvectorbool dp(n, vectorbool(n));int len 1, begin 0;for(int i n - 1; i 0; i--){for(int j i; j n; j){if(s[i] s[j]) dp[i][j] i 1 j ? dp[i 1][j - 1] : true;if(dp[i][j] j - i 1 len){len j - i 1;begin i;}}}return s.substr(begin, len);}
};中心探测法 class Solution {
public:string longestPalindrome(string s) {string RetStr;for(int i0;is.size();i){//回文串为奇数int lefti-1;int righti1;while(left0rights.size()s[left]s[right]){left--;right;}if(RetStr.size()right-left-1){//babad//01234 letf-1 i1 right3RetStrs.substr(left1,right-left-1);}//回文串为偶数lefti;righti1;while(left0rights.size()s[left]s[right]){left--;right;}if(RetStr.size()right-left-1){RetStrs.substr(left1,right-left-1);}}return RetStr;}
};分割回文串 IV 代码
class Solution {
public:bool checkPartitioning(string s) {int n s.size();vectorvectorbool dp(n, vectorbool(n));int count 0;for(int i n - 1; i 0; i--){for(int j i; j n; j){if(s[i] s[j] ) dp[i][j] i 1 j ? dp[i 1][j - 1] : true;}}//枚举第二个字符串的起始位置和结束位置for(int i 1; i n - 1; i) //前后留一个字符给第一个字符串{for(int j i; j n - 1; j)//结束位置从i开始到n - 1{if(dp[0][i - 1] dp[i][j] dp[j 1][n - 1] ) return true;}}return false;}
};分割回文串 II 题目分析 代码
class Solution {
public:int minCut(string s) {int n s.size();vectorvectorbool is_pal(n, vectorbool(n));int ret 0;//把所有子串是不是回文串放到is_pal中for(int i n - 1; i 0; i--){for(int j i; j n; j){if(s[i] s[j]) is_pal[i][j] i 1 j ? is_pal[i 1][j - 1] : true;}}vectorint dp(n, INT_MAX);for(int i 0; i n; i){if(is_pal[0][i]) dp[i] 0;// [0, i] 不是回文串else{for(int j 1; j i; j){if(is_pal[j][i]) dp[i] min(dp[i], dp[j - 1] 1);}}}return dp[n - 1];}
};最长回文子序列 题目分析 代码
class Solution {
public:int longestPalindromeSubseq(string s) {int n s.size();vectorvectorint dp(n, vectorint(n));//填表从下到上左到右填for(int i n - 1; i 0; i--){dp[i][i] 1; // i jfor(int j i 1; j n; j){if(s[i] s[j]){if(i 1 j) dp[i][j] 2;else if(i 1 j) dp[i][j] dp[i 1][j - 1] 2;}else{dp[i][j] max(dp[i][j - 1], dp[i 1][j]);}}}return dp[0][n - 1];}
};让字符串成为回文串的最少插入次数 题目分析 class Solution {
public:int minInsertions(string s) {int n s.size();vectorvectorint dp(n, vectorint(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(dp[i 1][j] 1, dp[i][j - 1] 1);}}}return dp[0][n - 1];}
};
