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])
如果是计算回文子序列个数，则依次中心扩展。 主要是要考虑两个元素的情况。这里我统一考虑该元素和他的左元素进行扩展。
你如果觉得你的实习经历质量不够可以找我之前跟的老师，可以包装大厂项目，这样你还有更多机会
投递字节跳动等公司8个岗位
字节跳动开奖360人在聊