力扣647-回文子串（Java详细题解）
题目链接：力扣647-回文子串
前情提要：
因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。
dp五部曲。
1.确定dp数组和i下标的含义。
2.确定递推公式。
3.dp初始化。
4.确定dp的遍历顺序。
5.如果没有ac打印dp数组 利于debug。
每一个dp题目如果都用这五步分析清楚，那么这道题就能解出来了。
题目思路:
本题是让我们返回字符串s中的回文子串的数目。
开始我们的dp五部曲。
1.确定dp数组和i下标的含义。
如果大家做了很多这种子序列相关的题目，在定义dp数组的时候 很自然就会想题目求什么，我们就如何定义dp数组。
绝大多数题目确实是这样，不过本题如果我们定义，dp[i] 为 下标i结尾的字符串有 dp[i]个回文串的话，我们会发现很难找到递归关系。
dp[i] 和 dp[i-1] ，dp[i + 1] 看上去都没啥关系。
我们应该按照回文串的性质来定义dp数组。
如果该串的首尾元素相同，那么只要判断中间元素是否回文，那么整个串都是回文的。
这样其实我们就已经得出来一个递推公式了。
所以为了明确这种递推关系，我们的dp数组是要定义成二维dp数组。
布尔类型的dp[i] [j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i] [j]为true，否则为false。
2.确定递推公式。
首先我们要分析以i下标的字符和以j下标的字符是否相同。
这里就有俩种情况。
-
不相同
肯定就不是回文串了，就默认false就行。
-
相同
相同其实还有三种情况。
- 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串。
- 情况二：下标i 与 j相差为1，例如aa，也是回文子串。
- 情况三：下标i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1] [j - 1]是否为true。
所以递推公式为：
if(s.charAt(i) == s.charAt(j)){if(j - i <= 1){dp[i][j] = true;result ++;}else{if(dp[i + 1][j - 1] == true){dp[i][j] = true;result ++;}}}
3.dp初始化。
注意dp数组定义为区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i] [j]为true，否则为false。
dp[i] [j]可以初始化为true么？ 当然不行，怎能刚开始就全都匹配上了。
所以全部定义为false。
4.确定dp的遍历顺序。
由递推公式可知dp[i] [j]是由dp[i +1] [j - 1]推出，在二维dp数组中就是由它的左下方推出。
所以遍历顺序一定为从下到上，从左到右。
5.如果没有ac打印dp数组 利于debug。
最终代码：
class Solution {public int countSubstrings(String s) {int result = 0;//根据回文串的性质//如果首尾俩个元素相同，那么只要判断中间元素是否是回文，那么整个串都是回文的。//这样我们就找到了一个推导方向。//dp数组定义的是i到j范围内是否是回文串boolean dp [][] = new boolean[s.length() + 1][s.length() + 1];//dp数组初始化为false//遍历顺序可有讲究，因为递推公式可以看出，dp[i][j]是由dp[i + 1][j - 1]推出。//在二维里就是从他的右下方推出来//所以我们遍历顺序肯定是从上到下从左到右 只要判定为回文 那么直接计数加1即可for(int i = s.length() - 1;i >=0 ;i--){for(int j = i;j < s.length();j ++){if(s.charAt(i) == s.charAt(j)){if(j - i <= 1){dp[i][j] = true;result ++;}else{if(dp[i + 1][j - 1] == true){dp[i][j] = true;result ++;}}}}}return result;}
}
这一篇博客就到这了，如果你有什么疑问和想法可以打在评论区，或者私信我。
我很乐意为你解答。那么我们下篇再见！