学习资料：https://programmercarl.com/0647.回文子串.html#算法公开课
动态规划最后一部分：回文字符串
子串是从原字符串中连续截取的；子序列可以是从原字符串中不连续提取出元素构成的
学习记录：
647.回文子串（难构造dp数组，dp数组是从原字符串截取[i,j]范围的片段是否是回文字符串，布尔变量；这样构造才能推出递推公式，就是当前值是二维数组中它的左下角的值来推导出来的）
点击查看代码
class Solution(object):
def countSubstrings(self, s):
"""
:type s: str
:rtype: int
"""
# 解法一：动态规划
# dp[i][j]代表[i,j]对应的s的片段是否为回文子串，值为false/true
# 若首尾相等s[i]==s[j],则有三种情况s='a'则i==j；若s='aa',则i+1==j；若s='abxxxa'，则j-i>1
# 构造dp二维数组
dp = [[False]*len(s) for _ in range(len(s))]
# 初始化，略过
# 实时更新回文子串个数
result = 0
# 开始遍历（从下到上，从左到右）
# 难点：这里i倒序遍历是因为递推公式的第二种情况，要先知道dp[i+1][j-1]再求dp[i][j]，相当于从左下角推导至当前值
for i in range(len(s)-1, -1, -1): # 第二个-1代表截至0
for j in range(i, len(s)): # !!!!!!! j也就是横坐标从i开始增加，因为dp[i][j]是从i到j !!!!!
if s[i] == s[j]:
if j-i<=1: # 合并情况一、二（必然是回文子串）
result += 1
dp[i][j] = True
elif dp[i+1][j-1]: # 情况三（此情况下，如果中间段是回文子串，则向外扩宽1后认为回文子串）
result += 1
dp[i][j] = True
return result
# 解法二：双指针（略）
516.最长回文子序列（可以不连续，所有dp数组代表原字符串在[i,j]范围内的片段中回文子序列的最长长度；这样构造是为了更好的得到递推公式）
点击查看代码
class Solution(object):
def longestPalindromeSubseq(self, s):
"""
:type s: str
:rtype: int
"""
# 动态规划，这道题回文子序列是可以从s中不连续提取元素来构成的
# dp[i][j]代表[i,j]范围内回文子序列的最长长度
# 构造二维dp数组
dp = [[0]*len(s) for _ in range(len(s))]
# 初始化，因为[i,j]范围内找回文子序列肯定是向中间靠拢的，那最中间是遍历不到的，需要初始化
for i in range(len(s)):
dp[i][i] = 1 # 一个字母也是一个回文子序列，长度为1
# 开始遍历，同理因为由左下角推导本位置，i从下到上，j从i+1开始然后从左到右遍历
for i in range(len(s)-1, -1, -1):
for j in range(i+1, len(s)): # 前面初始化过[i][i]的情况，这里从i+1开始
# 判断逻辑
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2 # 在中间片段的回文子序列基础上加i和j对应值，就是+2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1]) # 相当于添加任意一边的元素后，回文子序列不变
return dp[0][len(s)-1] # 返回从0到末尾的回文子序列的最长长度
PS:动态规划终于学完了，好充实的题量，前面背包那些很多没懂，后面股票、子序列问题能听懂，但是想不到要讨论的那么多情况。还需多刷呀。
今天天气阴，吃了好吃的粤菜早茶，货真价值味道也好，就是给我腻的嘞，还是浅尝比较适合我，赶紧来了个豌杂面缓过来了。