目录
写在最前：
1. 首先我们要考虑一个问题：如何判断一个字符串是回文子串
2.如何创建dp[i][j]表示回文子串
3. 如何初始化？
4. 如何实现
问题引入：
LCR 020. 回文子串
给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc" 输出：3 解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa" 输出：6 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
1 <= s.length <= 1000s由小写英文字母组成
为什么要将回文子串转为二维dp？
~~~ 方便解题，可以面对一系列的回文串的题目！
~~~ 算是一种比较好理解的答案。比起其他操作
~~~ 代码比较好记好背
写在最前：
对于设计到二维数组的遍历时，我们可以不要一下子就扎进代码里面。是要先理清楚他的遍历顺序和遍历的目的。为啥子要这样遍历。以及遍历的这个数组dp[i][j]代表的含义。不要一开始就研究当i=0时，j等于0,1,2。。。。这样往往会使我们陷入一些细节无法自拔。
1. 首先我们要考虑一个问题：如何判断一个字符串是回文子串
回文子串就是从左往右读和从右往左读相同的字符串。
2.如何创建dp[i][j]表示回文子串
比如s="abbab"
dp的长度是len(s)
dp[i][j]的含义:?
dp[i][j]==1表示字符串s[i]到s[j]是回文串
动态转移方程式：
dp[i][j]==true if dp[i+1][j-1]==true and s[i][j]
为什么是这个方程式？
不难理解对于子串s[1:6],只有当s[2,5]是回文子串时，并且s[1]==s[5]时才能构成回文子串。这里需要记住这个s[i]==s[j],当i==j时。
3. 如何初始化？
当i==j时，初始化dp[i][j]==true或者1，这样说可能有点抽象。当i==j时，s[i]与是[j]都表示同一字符。画个图
| 0(a) | 1(b) | 2(b) | 3(a) | 4(b) | |
| 0(a) | 1 | ||||
| 1(b) | 1 | ||||
| 2(b) | 1 | ||||
| 3(a) | 1 | ||||
| 4(b) | 1 |
---接着我们再初始化相邻元素相同的字符串aa,bb,cc这种，对于abbab,前两个b对应的赋值为1或true。
---初始化aba,bcb,opo这种，隔着一个元素左右两个元素是相同的回文串。这种初始化就是。
当s[i]==s[j] and j-i<2时，dp[i][j]==1或true。
[这里有一个需要注意的点：如果我们要统计的出现的回文子串的个数，我们不能重复统计，不能重复统计。比如dp[1][3]表示字符s[1]到s[3]是回文子串，就不能统计dp[3][1]是回文子串。也就是说我们只需要计算上三角矩阵或者下三角矩阵。
| 0(a) | 1(b) | 2(b) | 3(a) | 4(b) | |
| 0(a) | 1 | 1 | 1 | ||
| 1(b) | 1 | ||||
| 2(b) | 1 | 1 | |||
| 3(a) | 1 | ||||
| 4(b) | 1 |
4. 如何实现
我们可以实现这样的一种遍历方式:i是行，j是列。填完这个dp数组的顺序是这样
从1到15是遍历的顺序 。当然，你也可以有其他的遍历顺序，这个无所谓。 只要能理清楚为什么是只遍历一半的数组。
只遍历右上三角的元素，遍历的范围从小到大。比如abbab
代码实现
python版
def count_substrings(s):n = len(s)s_list = list(s)res = 0dp = [[0 for _ in range(n)] for _ in range(n)]for j in range(n):for i in range(j, -1, -1):print(f'j={j},i={i}')if s_list[i] == s_list[j] and ((j - i < 3) or dp[i + 1][j - 1]):dp[i][j] = Trueres += 1for i in dp:print(i)return res
count_substrings("abbab")ps：对于不熟悉的朋友可以打印一下i,j的值来具体理解。
java版
public int countSubstrings(String s) {int n=s.length();char sChar[]=s.toCharArray();int res=0;boolean dp[][]=new boolean [n][n];for(int j=0; j<n; j++){for(int i=j;i>=0;i--){if(sChar[i]==sChar[j] && (j-i<3 || dp[i+1][j-1])) {dp[i][j]=true;res++;}}}return res;}
