四川省城乡建设网站,wordpress企业外贸主题,网站内页模板,公关到底做什么文章目录 动态规划理论基础动规五部曲#xff1a;出现结果不正确#xff1a; 1. 647回文子串2. 516最长回文子序列 动态规划理论基础
动规五部曲#xff1a;
确定dp数组 下标及dp[i] 的含义。递推公式#xff1a;比如斐波那契数列 dp[i] dp[i-1] dp[i-2]。初始化dp数组… 文章目录 动态规划理论基础动规五部曲出现结果不正确 1. 647回文子串2. 516最长回文子序列 动态规划理论基础
动规五部曲
确定dp数组 下标及dp[i] 的含义。递推公式比如斐波那契数列 dp[i] dp[i-1] dp[i-2]。初始化dp数组。确定遍历顺序从前到后or其他。打印。
出现结果不正确
打印dp日志和自己想的一样递推公式、初始化或者遍历顺序出错。打印dp日志和自己想的不一样代码实现细节出现问题。
1. 647回文子串 参考文档代码随想录 分析 判断一个字符串里面的有多少个回文串需要二维dp数组dp[i][j]表示字符串s的[i, j]之间有多少个回文字符串。当s[i] s[j]的时候有可能是回文串i j 或者 i和j相差一个时是回文串如果i和j相差的大于1则需要判断[i1, j-1]是否是回文串了。而当s[i] ! s[j]的时候s的[i, j]肯定不是回文串这也表示dp的初始化是false。
dp五部曲
dp[i][j]含义表示s[i, j]回文串的个数。统计一个字符串中回文串的个数使用的是bool型的数组如果dp[i][j] true那么最终的回文串个数加1而不是记录有多少个回文子串。数组类型的设计也很有意思。递推公式if(s[i] s[j]) { if(j - i 1) {dp[i][j] true; } else { dp[i][j] dp[i1][j-1]; } }初始化dp[i][j] false;遍历顺序根据递推公式可以得知当前的dp[i][j]有可能需要借助左下方的dp[i1][j-1]所以遍历顺序是从下到上先更新下面一行的数据之后从左到右先更新左侧的数据。
代码
class Solution {
public:int countSubstrings(string s) {//dp[i]: 以i结尾的回文子串的个数tvectorvectorbool dp(s.size(), vectorbool(s.size(), false));int sum 0;//注意遍历的顺序是从下到上从左到右的for(int i s.size() - 1; i 0; i--){for(int j i; j s.size(); j){if(s[i] s[j]) {if(j - i 1) {dp[i][j] true;sum;}else if(dp[i1][j-1]){dp[i][j] true;sum;}}}}return sum;}
};2. 516最长回文子序列 参考文档代码随想录 分析 和上一题回文子串不同的地方在于这次的回文子序列不要求是连续的。所以还采用和上一题一样的方法使用二维的dp数组。但是为了更新回文子串的长度需要将数组的类型设为int型。
dp五部曲
dp[i][j]含义表示字符串s中[i, j]之间的最长回文子序列。递推公式if(s[i] s[j]) dp[i][j] dp[i1][j-1] 2; else dp[i][j] max(dp[i1][j], dp[i][j-1]); 初始化dp[i][i] 1。其余为0。遍历顺序根据递推公式遍历顺序是从下到上先把下一行的数据更新好根据下一行的数据更新本行的数据从左到右先更新左侧的数据根据左侧的数据更新本位置的数据。 代码
class Solution {
public:int longestPalindromeSubseq(string s) {//返回最长回文串的长度数组类型是int型vectorvectorint dp(s.size(), vectorint(s.size(), 0));//初始化for(int i 0; i s.size(); i) dp[i][i] 1;//更新dpfor(int i s.size() - 1; i 0; i--){for(int j i 1; j s.size(); j){if(s[i] s[j]) dp[i][j] dp[i1][j-1] 2;else{dp[i][j] max(dp[i1][j], dp[i][j-1]);}}}return dp[0][s.size() - 1];}
};
