day 46 | 回文序列
两道题目 分别是最长回文子序列的长度和个数。
当说回文子序列的时候有一个注意点就是 aa 这种也算是一个回文子序列。
在用动规解题的时候，我们会划分子问题来解决。 如果一个字符串是子序列，那么去掉首位仍然是子序列。
如果要让 aa 也符合的话，我们就可以让空字符串也为子序列。
由此可以得到最长的长度是这样的表达式
if s[i]==s[j]: dp[i][j]=dp[i+1][j-1]+2 else: dp[i][j]=max(dp[i+1][j],dp[i][j-1])
如果是计算回文子序列个数，则依次中心扩展。 主要是要考虑两个元素的情况。这里我统一考虑该元素和他的左元素进行扩展。
水滴公司氛围 17人发布