这里要注意的是我们的遍历顺序，不能是i一遍，j一遍这样，因为会包含后面的信息
所以我们这里选择的是先遍历长度，然后再遍历首字符
classSolution:defcountSubstrings(self,s:str)->int:n=len(s)dp=[[Falsefor_inrange(n+1)]for_inrange(n+1)]ans=nforiinrange(n+1):dp[i][i]=Trueforlinrange(2,n+1):foriinrange(n-l+1):ifs[i]==s[i+l-1]:ifi+1<=i+l-2:ifdp[i+1][i+l-2]:dp[i][i+l-1]=Trueans+=1else:dp[i][i+l-1]=Trueans+=1returnans参考答案非常机智！！！
首先看这幅图，在我们需要知道dp[i][j]是否为回文子串的前提是知道dp[i+1][j-1]
所以！！！
i是从大到小进行遍历，j是从小到大进行遍历。所以！！非常有意思。
并且在进行判断的时候，使用i-j<=1然后进行dp[i][i+l-1]=True，这样的话可读性更强
classSolution:defcountSubstrings(self,s:str)->int:dp=[[False]*len(s)for_inrange(len(s))]result=0foriinrange(len(s)-1,-1,-1):#注意遍历顺序forjinrange(i,len(s)):ifs[i]==s[j]and(j-i<=1ordp[i+1][j-1]):result+=1dp[i][j]=Truereturnresult双指针法动态规划的空间复杂度是偏高的，我们再看一下双指针法。
首先确定回文串，就是找中心然后向两边扩散看是不是对称的就可以了。
在遍历中心点的时候，要注意中心点有两种情况。
一个元素可以作为中心点，两个元素也可以作为中心点。
那么有人同学问了，三个元素还可以做中心点呢。其实三个元素就可以由一个元素左右添加元素得到，四个元素则可以由两个元素左右添加元素得到。
所以我们在计算的时候，要注意一个元素为中心点和两个元素为中心点的情况。
classSolution:defcountSubstrings(self,s:str)->int:result=0foriinrange(len(s)):result+=self.extend(s,i,i,len(s))#以i为中心result+=self.extend(s,i,i+1,len(s))#以i和i+1为中心returnresultdefextend(self,s,i,j,n):res=0whilei>=0andj ifs[i]==s[j]:dp[i][j]=dp[i+1][j-1]+2 ifs[i]!=s[j]:dp[i][j]=max(dp[i+1][j],dp[i][j-1]) 一个从正面，一个反面 j>i classSolution:deflongestPalindromeSubseq(self,s:str)->int:dp=[[0]*len(s)for_inrange(len(s))]foriinrange(len(s)):dp[i][i]=1foriinrange(len(s)-1,-1,-1):forjinrange(i+1,len(s)):ifs[i]==s[j]:dp[i][j]=dp[i+1][j-1]+2else:dp[i][j]=max(dp[i+1][j],dp[i][j-1])returndp[0][-1] 动规五部曲分别为： 动规专题刚开始的时候，讲的题目比较简单，不少录友和我反应：这么简单的题目讲的复杂了，不用那么多步骤分析，想出递推公式直接就AC这道题目了。