门户网站的建设公司,台山网站定制,做狗狗网站的背景图,复杂的手游app要多少钱动态规划算法14
LeetCode 647 回文子串 2023.12.20
题目链接代码随想录讲解[链接]
int countSubstrings(string s) {//暴力搜索#xff0c;前两层遍历确定子字符串的起始和末尾位置//第三层循环判断当前子字符串是否为回文串/*int result 0;for (int i 0; i s.size…动态规划算法14
LeetCode 647 回文子串 2023.12.20
题目链接代码随想录讲解[链接]
int countSubstrings(string s) {//暴力搜索前两层遍历确定子字符串的起始和末尾位置//第三层循环判断当前子字符串是否为回文串/*int result 0;for (int i 0; i s.size(); i){for(int j i; j s.size(); j){//sym变量用于记录判断结果当不是回文串时sym值变int sym 1;for (int k i; k (ji)/2; k){if(s[k] ! s[j-(k-i)]){sym 0;break; }}if(sym 1)result;}}return result;*///动态规划//result存储s字符串中回文子串的个数int result 0;//1确定二维dp数组dp[i][j]表示s[i, j]子串是否为回文串vectorvectorbool dp(s.size(), vectorbool(s.size(), false));//3初始化根据递推公式含义dp所有值默认值为false//2确定递推公式 4确定遍历顺序//dp[i][j]由dp[i1][j-1]得出那么二层循环先倒序后正序for (int i s.size()-1; i 0; i--){for(int j i; j s.size(); j){//递推公式:当s[i, j]子字符串首尾元素相同时//当j-i1时那么说明只有一个元素或者三个元素中首尾元素相同//当j-i1时判断s[i1, j-1]是否为回文串如果是那么s[i, j]也是回文串if(s[i] s[j]){if(j-i 1){dp[i][j] true;result;}else{if(dp[i1][j-1]){dp[i][j] true;result;}}}}}return result;
}LeetCode 517 最长回文子序列 2023.12.20
题目链接代码随想录讲解[链接]
int longestPalindromeSubseq(string s) {//1确定dp数组dp[i][j]表示s[i, j]区间内最长回文子序列的长度vectorvectorint dp(s.size(), vectorint(s.size(), 0));//3初始化根据递推公式含义需要对ij时dp[i][j]赋值长度为1for (int i 0; i s.size(); i)dp[i][i] 1;//2确定递推公式 4确定遍历顺序//dp[i][j]由dp[i1][j-1]、dp[i1][j]、dp[i][j-1]得出那么二层循环先倒序后正序for (int i s.size()-1; i 0; i--){for(int j i 1; j s.size(); j){//当s[i] s[j]时dp[i][j]dp[i1][j-1]i,j两个字符长度if(s[i] s[j])dp[i][j] dp[i1][j-1] 2;//当s[i] s[j]时dp[i][j]max(在dp[i1][j-1]基础上加s[i]或s[j]的最长回文子序列长度)elsedp[i][j] max(dp[i1][j], dp[i][j-1]);}}//返回s[0,s.size()-1]的最长回文子序列长度return dp[0][s.size()-1];
}
