广州海珠网站建设,有没有做网站的随州,微信公众号怎么做推送,景洪市新农村建设网站一、647. 回文子串 题目链接/文章讲解#xff1a;代码随想录 思考#xff1a; 1.确定dp数组#xff08;dp table#xff09;以及下标的含义 如果本题定义dp[i] 为 下标i结尾的字符串有 dp[i]个回文串的话#xff1a; 会发现很难找到递归关系#xff0c;dp[i] 和 dp[i-1]…一、647. 回文子串 题目链接/文章讲解代码随想录 思考 1.确定dp数组dp table以及下标的含义 如果本题定义dp[i] 为 下标i结尾的字符串有 dp[i]个回文串的话 会发现很难找到递归关系dp[i] 和 dp[i-1] dp[i 1] 看上去都没啥关系因此本题要从回文字符串的性质着手。 可以找到一种递归关系 也就是判断一个子字符串字符串的下表范围[i,j]是否回文依赖于子字符串下表范围[i 1, j - 1] 是否是回文为了明确这种递归关系dp数组要定义成一位二维dp数组 bool dp[i][j]表示区间范围[i,j] 注意是左闭右闭的子串是否是回文子串如果是dp[i][j]为true否则为false。 2.确定递推公式 整体上是两种情况就是s[i]与s[j]相等、不相等 当s[i] s[j]dp[i][j] false。 当s[i] ! s[j]有如下三种情况 情况一下标i 与 j相同是同一个字符例如a是回文子串情况二下标i 与 j相差为1例如aa也是回文子串情况三下标i 与 j相差大于1的时候例如cabac此时s[i]与s[j]已经相同了要看i到j区间是不是回文子串就看aba是不是回文就可以了那么aba的区间就是 i1 与 j-1区间这个区间是不是回文就看dp[i 1][j - 1]是否为true。 if (s[i] s[j]) {if (j - i 1) { // 情况一 和 情况二result;dp[i][j] true;} else if (dp[i 1][j - 1]) { // 情况三result;dp[i][j] true;}
} 3.dp数组的初始化 dp[i][j]初始化为false 4.确定遍历顺序 从递推公式中可以看出情况三是根据dp[i 1][j - 1]是否为true在对dp[i][j]进行赋值true的。dp[i 1][j - 1] 在 dp[i][j]的左下角如图 从下到上从左到右遍历这样保证dp[i 1][j - 1]都是经过计算的。 for (int i s.size() - 1; i 0; i--) { for (int j i; j s.size(); j) { 5.举例推导dp数组 代码实现
class Solution {
public:int countSubstrings(string s) {vectorvectorbool dp(s.size(), vectorbool(s.size(), false));int result 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) { // 情况一 和 情况二result;dp[i][j] true;} else if (dp[i 1][j - 1]) { // 情况三result;dp[i][j] true;}}}}return result;}
};
时间复杂度O(n^2)空间复杂度O(n^2) 二、516.最长回文子序列 题目链接/文章讲解代码随想录 思考本题和回文子串思路其实差不多但比求回文子串简单一点因为情况少了一点 1.确定dp数组dp table以及下标的含义 dp[i][j]字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。 2.确定递推公式 如果s[i]与s[j]相同dp[i][j] dp[i 1][j - 1] 2; 如果s[i]与s[j]不相同dp[i][j] max(dp[i 1][j], dp[i][j - 1]) 不相同说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。 加入s[j]的回文子序列长度为dp[i 1][j]。 加入s[i]的回文子序列长度为dp[i][j - 1]。 那么dp[i][j]一定是取最大的即dp[i][j] max(dp[i 1][j], dp[i][j - 1]); if (s[i] s[j]) {dp[i][j] dp[i 1][j - 1] 2;
} else {dp[i][j] max(dp[i 1][j], dp[i][j - 1]);
} 3.dp数组的初始化 从递推公式dp[i][j] dp[i 1][j - 1] 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况所以需要手动初始化一下当i与j相同那么dp[i][j]等于1其他情况dp[i][j]初始为0 vectorvectorint dp(s.size(), vectorint(s.size(), 0));
for (int i 0; i s.size(); i) dp[i][i] 1; 4.确定遍历顺序 dp[i][j] 依赖于 dp[i 1][j - 1] dp[i 1][j] 和 dp[i][j - 1] 所以遍历i的时候一定要从下到上遍历j可以正常从左向右遍历。 for (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[i 1][j - 1] 2;} else {dp[i][j] max(dp[i 1][j], dp[i][j - 1]);}}
} 5.举例推导dp数组 代码实现
class Solution {
public:int longestPalindromeSubseq(string s) {vectorvectorint dp(s.size(), vectorint(s.size(), 0));for (int i 0; i s.size(); i) dp[i][i] 1;for (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[i 1][j - 1] 2;} else {dp[i][j] max(dp[i 1][j], dp[i][j - 1]);}}}return dp[0][s.size() - 1];}
};
时间复杂度: O(n^2)空间复杂度: O(n^2) 三、动态规划总结篇 题目链接/文章讲解代码随想录
