代码随想录算法训练营第四十六天｜ 647. 回文子串，516.最长回文子序列，动态规划总结

647. Palindromic Substrings

在left and right element same的情况下，只要中间的字符串是回文string，向两边拓展的就是回文字串

dp[i][j]: [i, j]这个子串是否是回文子串substring

if s[i] == s[j]:

有三种情况：1. i==j， 2. j-i = 1, 3. j-i > 1

这次的顺序是从下往上，从左往右

使用双指针的话，能发现可以分成odd number 回文 & 偶数回文两种情况

其实carl用的extend function就是把这两种情况给用function表达了出来

516. Longest Palindromic Subsequence

如果使用上一题的思路

dp[i][j]表示s[i:j]中longest palindromic subsequence的最长长度

if s[i] == s[j]:

if i == j:

dp[i][j] = 1

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+1][j], dp[i][j-1], dp[i+1][j-1])

对着这套逻辑居然写出来了