647. 回文子串
这道题不能以一个一维数组来表示回文字串的数目，如dp[i]表示为 下标i结尾的字符串有 dp[i]个回文串的话很难找到递归关系。因为你不清楚引入下标 str[i+1] 后，当前dp[i+1]与dp[i]的数量关系。要抓住回文字串的特征，回文串的特征在于对称。因此可以通过定义一个二维数组dp[i][j]来定义和判断下标为i 到下标为j的字符串str[i: j+1]是否是回文子串。
思路：
如果 [i], [seq], [j] 中 [seq] 已经被判定是回文子串了，那么如果 [i] == [j]，此时就可以判定 ( [i],[seq],[j] )构成的整个字符串就是回文子串。
1. dp数组定义
- dp[i][j]: 表示从 下标i 到 下标j 所表示的字符串 是否是回文字串
2. 递推公式
if str[i] == str[j]:
if j - i <= 1: ### 长度小于等于2的字符串容易判断出是否是回文子串
dp[i][j] = True
result += 1
else:
if dp[i+1][j-1] == True:
dp[i][j] = True
result += 13. dp初始化
- 初始化为一个全False的二维数组
4. 遍历顺序
- 根据dp[i][j]的递推公式(if str[i] == str[j] and dp[i+1][j-1] == True then dp[i][j] = True)可知，i得从大到小进行遍历，j得从小到大进行遍历
另外，要注意 j >= i，因此在对 j 进行循环遍历时要注意循环的起始位置。
i == j 的时候，表示当前判断的是同一个位置，即判断的是一个字符。
5. 打印dp数组
- result 用于统计回文子串的数目
- dp用于统计回文子串的位置
Code
class Solution(object):
def countSubstrings(self, s):
"""
:type s: str
:rtype: int
"""
length = len(s)
dp = [ [False] * len(s) for _ in range(len(s)) ]
result = 0
for i in range(len(s)-1,-1,-1):
for j in range(i, len(s)):
if s[i] == s[j]:
if j - i <= 1:
dp[i][j] = True
result += 1
else:
if dp[i+1][j-1] == True:
dp[i][j] = True
result += 1
# for i in range(len(s)):
# print(dp[i])
# print(dp)
return result516.最长回文子序列
与上一题相比，区别在于 序列 和 子串。序列是只要相对顺序是正确就行，子串一定是要绝对顺序是正确的，如bbbab，最长回文子序列是bbbb，最长回文子串是bbb。
因此，与上一题相比，关键在于进行删除操作。
关键在于dp数组的定义，要明白与647的区别。dp数组定义正确的话，后面递推公式递推出来后就知道如何开展工作了。647如果 dp[i][j] 定义为 [i,j] 之间的最长回文子串数目的话，其实也能做，递推公式如下：
dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
if str[i] == str[j]:
dp[i][j] += 1但这样的话，感觉理解起来不如（dp[i][j]: 表示从 下标i 到 下标j 所表示的字符串 是否是回文字串）简单，后者基于dp数组的定义可以较为清楚地得出递推公式。
思路：
1. dp数组定义.
dp[i][j] 表示以 [i,j] 之间的最长回文子序列长度
2. 递推公式
if s[i] == s[j]: ## 不进行删除操作
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i][j-1], dp[i+1][j]) ## 进行删除操作，取最大由于s[i] != s[j]：
因此对于这两个元素，我们可以对其其中一个进行删除操作来得到 [i,j] 内的最大回文子序列长度
dp[i][j] = dp[i][j-1]：表示删除 第 j 个元素，只考虑 [i, j-1] 内的最大回文子序列长度
dp[i][j] = dp[i+1][j]：表示删除 第 i 个元素，只考虑 [i+1, j]内的最大回文子序列长度
3. dp初始化
最小的回文子序列为一个字符的大小。
for i in range(length):
dp[i][i] = 1 # 最小的回文子序列为一个字符的大小为什么要初始化 i == j 的情况是因为第二个循环是从i+1开始遍历操作的，在此过程中i 和 j 会不断逼近，但始终构不成 i == j。
4. 遍历顺序
从下到上，从左到右。
为什么与647相比，本题第二个循环从 i+1开始，因为647的第二个循环 i == j 的情况起到了初始化的作用，只不过一并放到第二个循环进行操作而已，如果提前初始化了，则647的第二个循环也是从i+1开始。在这道题中，我们已经初始化了 i==j 的情况，因此第二个循环要从 i + 1 开始。
5. 打印dp数组。
dp [0][-1] 表示整个字符串内的最大序列长度。
Code
class Solution(object):
def longestPalindromeSubseq(self, s):
"""
:type s: str
:rtype: int
"""
length = len(s)
dp = [ [0] * length for _ in range(length) ]
for i in range(length):
dp[i][i] = 1 # 最小的回文子序列为一个字符的大小
for i in range(length-1,-1,-1):
for j in range(i+1,length):
if s[i] == s[j]: ## 不进行删除操作
if j-i == 1:
dp[i][j] = 2
else:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i][j-1], dp[i+1][j]) ## 进行删除操作，后判断取最大
return dp[0][length-1]