建立网站的目录结构应注意哪些问题,网站模版 源码之家,深圳做外贸网站公司哪家好,专业网站设计立找亿企邦● 647. 回文子串
1.dp数组含义。
之前的题目#xff0c;差不多都是求什么就怎么定义dp数组#xff0c;最后返回dp的最后一个元素。但是这里如果定义一维数组dp[i]是[0,i]范围的回文子串的个数的话#xff0c;怎么根据dp[i-1]得到dp[i]#xff1f;发现很难找到递归关系…● 647. 回文子串
1.dp数组含义。
之前的题目差不多都是求什么就怎么定义dp数组最后返回dp的最后一个元素。但是这里如果定义一维数组dp[i]是[0,i]范围的回文子串的个数的话怎么根据dp[i-1]得到dp[i]发现很难找到递归关系回文串需要固定两端来讨论判断。
所以需要二维数组。又dp数组不统计个数而是判断是否是回文子串的话比较好推导递归关系因为根据回文子串的定义如果下标1、2、3组成的子串是回文串那么只需要下标0和4的字符相等就可以判定为回文子串。而统计个数的话还是需要比较中间所有的元素。 所以dp[i][j]下标范围为[i,j]的子串是否回文是为true否为false。i、j都是闭区间当ij的时候就是单个字符好初始化。
最后返回dp数组中值为true的个数。
2.递推公式。
参照上图如果s[i]s[j]而且中间的子串[i1,j-1]是回文子串的话那么[i,j]子串肯定是回文子串。这个图只考虑了i和j中间至少一个元素的情况实际上在相等的条件下根据i和j的大小得到dp[i][j]有3种情况
①ij就一个字符[i,j]是回文子串。
②ji12个字符只要满足一个条件s[i]s[j]就是一个回文子串。
③ji1有≥2个字符只要满足相等和dp[i1][j-1]true这两个条件的话[i,j]就是回文子串。
所以dp[i][j]在上面3种情况中true其他的都是false可以直接在初始化的时候设定。因为这里的条件且和或 的逻辑有点多所以就分开写
if(s[i]s[j]){if(j(i1))//情况1和2{dp[i][j]true;count;}if(in-1j0dp[i1][j-1]){//情况3dp[i][j]true;count;}
}
3.初始化。
在一开始定义dp数组的时候我们就所有元素都初始化为false到递推的时候再把每个元素更新为true。
注意情况①没有在初始化时设定本来这个递推比较耗时间在循环前面初始化的话有2个例子会超时。
4.遍历顺序。
这题的遍历顺序踩坑了其实这个dp数组是一个对称矩阵我们只需要统计对角线上true的个数加上左下角或者右上角的true个数即可。再看定义的时候我们说范围[i,j]内的所以定为ij即统计的是对角线右上角的。又因为dp[i][j]是否为true取决于dp[i1][j-1][i1,j-1]是在[i,j]的左下角说明到达i、j的时候左下角的dp是需要更新了的。所以在ij的前提下
1先列后行先j后i for(int j0;jn;j){for(int i0;ij;i){
}}
2先行后列先i后j for(int in-1;i0;--i){for(int ji;jn;j){
}}
告诉我们遍历顺序需要简画一下dp数组的结构图。
5.打印。
代码如下。列优先的情况需要增加条件in-1 j0行优先的话不需要添加。
class Solution {
public:int countSubstrings(string s) {int ns.size();int count0;vectorvectorbool dp(n,vectorbool(n,false));for(int j0;jn;j){for(int i0;ij;i){if(s[i]s[j]){if(j(i1)){dp[i][j]true;count;}if(in-1j0dp[i1][j-1]){dp[i][j]true;count;}}coutdp[i][j] ;}}return count;}
}; ● 516.最长回文子序列 ● 动态规划总结篇
