做网站网站名字自己设置吗,深圳市房屋管理局官方网站,百度搜索最多的关键词,服务 好的网站制作参考#xff1a;代码随想录
647. 回文子串
1. dp数组#xff08;dp table#xff09;以及下标的含义
是不是能找到一种递归关系#xff0c;也就是判断一个子字符串#xff08;字符串的下表范围[i,j]#xff09;是否回文#xff0c;依赖于#xff0c;子字符串#x…参考代码随想录
647. 回文子串
1. dp数组dp table以及下标的含义
是不是能找到一种递归关系也就是判断一个子字符串字符串的下表范围[i,j]是否回文依赖于子字符串下表范围[i 1, j - 1] 是否是回文
布尔类型的dp[i][j]表示区间范围[i,j] 注意是左闭右闭的子串是否是回文子串如果是dp[i][j]为true否则为false。
dp数组无法直接得出回文数量但是可以判断是否为回文如果是直接增加即可 2. 递推公式
整体上是两种就是s[i]与s[j]相等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。
其实情况12就包含了初始化预防了可能存在的边界溢出
3.初始化
由于已经有情况12考虑初始化的情况所以dp数组初始值就是默认值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]都是经过计算的。
class Solution {public int countSubstrings(String s) {char[] chars s.toCharArray();int len chars.length;boolean[][] dp new boolean[len][len];int result 0;for (int i len - 1; i 0; i--) {for (int j i; j len; j) {if (chars[i] chars[j]) {if (j - i 1) { // 情况一 和 情况二result;dp[i][j] true;} else if (dp[i 1][j - 1]) { //情况三result;dp[i][j] true;}}}}return result;}
}简化版
class Solution {public int countSubstrings(String s) {boolean[][] dp new boolean[s.length()][s.length()];int res 0;for (int i s.length() - 1; i 0; i--) {for (int j i; j s.length(); j) {if (s.charAt(i) s.charAt(j) (j - i 1 || dp[i 1][j - 1])) {res;dp[i][j] true;}}}return res;}
}
双指针法
动态规划的空间复杂度是偏高的我们再看一下双指针法。
首先确定回文串就是找中心然后向两边扩散看是不是对称的就可以了。
在遍历中心点的时候要注意中心点有两种情况。
一个元素可以作为中心点两个元素也可以作为中心点。 516.最长回文子序列
回文子串是要连续的回文子序列可不是连续的
递推公式
这个递推公式适用于求最大值的max而不是多少种方法的累加
如果s[i]与s[j]相同那么dp[i][j] dp[i 1][j - 1] 2;
如图 如果这里看不懂回忆一下dp[i][j]的定义
如果s[i]与s[j]不相同说明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]); 动态规划总结
