当前位置: 首页> 文旅> 艺术 > 网站大全免黄_常德百度seo_网络推广是什么_制作网站模板

网站大全免黄_常德百度seo_网络推广是什么_制作网站模板

时间:2025/7/13 13:14:37来源:https://blog.csdn.net/weixin_52151595/article/details/142616481 浏览次数:0次
网站大全免黄_常德百度seo_网络推广是什么_制作网站模板

今天是动态规划的最后一天,终于要结束折磨了!!!今天的两道题,第一道看视频做的,第二道自己AC的,开心!!!!

647. 回文子串

这道题不能用一维dp数组来做,必须用二维dp数组,我认为这道题目的dp数组定义很关键,这道题的dp数组定义为:字符串在s[i]-s[j]的范围的字符串片段是否为回文串(true or false), 递推公式也不难想,首先讨论一般情况:当s[i] == s[j]时,如果i和j相差很远,那么i和j范围内的字符串是否为回文子串就取决于i + 1和j - 1包围住的字符串是否为回文子串,所以有dp[i][j] = dp[i + 1][j - 1];如果j - i <= 1(相邻或者指向同一字符),此时对应"a"或者"aa"的情况,这个时候直接令dp[i][j] = true即可。如果s[i] != s[j]的话,直接令dp[i][j] = false。
这道题不太注重初始化条件,但是有一点,绝对不能全部初始化成true就行。
另外,这道题的遍历顺序一定一定要注意,从递推公式来看,是从左下角向右上角推导的,所以遍历的时候需要从左往右,从下往上遍历!!!

class Solution {
public:int countSubstrings(string s) {//1.确定dp[i][j]的含义:字符串在s[i]-s[j]的范围的字符串片段是否为回文串(true or false), //2.确定递推公式dp[i][j] = dp[i + 1][j - 1];//          or dp[i][j] = false;//3.dp数组初始化 dp[i][j] = false;//4.确定遍历顺序:从左往右,从下往上遍历//5.打印数组(省略)int m = s.size();vector<vector<bool>> dp(m, vector<bool> (m, false));int result = 0;for(int i = m - 1; i >= 0; i--){for(int j = i; j < m; j++){if(s[i] == s[j]){if(j - i <= 1){  //i == j || i == j - 1dp[i][j] = true;result++;}     else{dp[i][j] = dp[i + 1][j - 1];if(dp[i][j]) result++;}    }}}return result;}
};

516.最长回文子序列

这道题目和上一道题还是有差别的,首先题目问的是最长回文子序列,如果dp数组还是存储布尔值的话,无法体现出回文子序列的长度,因此本题dp数组的定义为:字符串在s[i]-s[j]的范围的字符串片段中最长回文子串的长度为dp[i][j],在递推公式上,如果s[i] == s[j],如果在i和j相差很大的情况下,则dp[i][j]应当在内侧的最长回文子序列的基础上加2,如果j - i <= 1的情况下,dp[i][j] = j - i + 1;如果s[i] != s[j],则i + 1, j包围的字符串或者i,j - 1包围的字符串中仍有可能存在回文子序列,所以需要对这两种情况取较大值,存入dp[i][j]中,即dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])。
在初始化上也没有特别需要注意的地方,遍历顺序依然是从左往右,从下往上。

class Solution {
public:int longestPalindromeSubseq(string s) {//1.确定dp[i][j]的含义:字符串在s[i]-s[j]的范围的字符串片段中最长回文子串的长度为dp[i][j],//2.确定递推公式dp[i][j] = dp[i + 1][j - 1] + 2;//          or dp[i][j] = dp[i + 1][j] || dp[i][j - 1];//3.dp数组初始化 dp[i][j] = false;//4.确定遍历顺序:从左往右,从下往上遍历//5.打印数组(省略)int m = s.size();int result = 0;vector<vector<int>> dp(m, vector<int> (m, 0));for(int i = m - 1; i >= 0; i--){for(int j = i; j < m; j++){if(s[i] == s[j]){if(j - i <= 1)dp[i][j] = j - i + 1;elsedp[i][j] = dp[i + 1][j - 1] + 2;}elsedp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);}}return dp[0][m - 1];}
};

动态规划完结撒花!!!!

关键字:网站大全免黄_常德百度seo_网络推广是什么_制作网站模板

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: