647. 回文子串 516. 最长回文子序列

647. 回文子串 

方法一：动态规划

        dp[i][j]:[i,j]范围的下标字符串s是否为回文子串

        遍历字符串，每次判断s[i]与s[j]是否相等

①若相等，j-i=0 即单个字符串s[i]，那么一定为回文子串，赋值为1 

②若相等，j-i=1 即两个相同字符串，那么也一定为回文子串，赋值为1

③若相等，j-i>1 子串的长度大于2，那么就要判断子串内侧的子串是否为回文子串，若是，则该子串为回文子串 即dp[i][j]=dp[i+1][j-1]

若不相等，则不为回文子串，dp值默认为0

        遍历顺序，i取决于i+1,i从下len往上0遍历，j取决于j-1，从左i往右len遍历。

        因此先遍历最后一个字符。

方法二：双指针法

        中心扩散法，i从前向后遍历

        ①每次以i为中心向左右扩散，若s[start]=s[end]则为一个回文串 （start=end=i）

        ②每次以[i,i+1]为中心向左右扩散，若s[start]=s[end]则为一个回文串(start=i,end=i+1)

        while (start >= 0 && end < size && s.charAt(start) == s.charAt(end)) {start--;end++;res++;}

516. 最长回文子序列 

        dp[i][j]:[i,j]范围内的s子串下标回文子串的长度

若s[i]=s[j],长度为[i+1,j-1]最长回文子串长度+2

否则不是回文子串，长度为[i+1,j]和[i,j+1]的最长回文子串长度 的较大值。

i取决于i+1，从下往上遍历，j取决j+1，从前往后遍历。

        初始化dp[i][i]=1 即单个字符长度为1

        i从len-1开始向前遍历，j从i+1开始向后遍历。

        最后返回最后遍历的dp[0][len-1]的值即为该字符串最长回文子串长度