闺蜜吐槽：对象年薪70w，被裁后5个月没找到下家，还让闺蜜节约开支，她直接说：暂时分手八，也能缓解你压力，等找到工作再回来。
虎哥约 4 分钟今天看到闺蜜吐槽她男朋友的事，真是让我有点想笑又有点心酸。
事情是这样的——她男朋友年薪70w，本来日子过得蛮滋润的，结果突然被裁员了。好像是那种公司“大裁员”模式，5个月了还没找到新的工作，而他现在开始让闺蜜节省开支。
哎，我就想问问，真的是这样吗？我觉得男生说的也没有毛病呀，总不能毫无节制的挥霍呀，当然如果女生是花自己的钱，咱就不能说啥了，但是如果靠男生养，还是要体谅一下男生，你说是吧！
算法题：最长回文子序列
嗨，大家好。今天要聊的是一个常见的算法题：最长回文子序列。
说到这个问题，很多小伙伴在刷题时可能都碰到过，尤其是在面试中，它也是一道经典的考题。想必很多人都在想，回文字符串听上去似乎不难，但是回文子序列又是啥？我们怎么解决这个问题？
一、回文子序列到底是什么？
先给大家普及一下知识。回文子序列指的是一个字符串中，按顺序排列但不要求连续的字符，可以构成一个回文串。什么是回文串呢？就是从前往后读和从后往前读完全一样的字符串。举个例子，"abac"这个字符串的回文子序列有："a", "b", "aba"等等。而最长回文子序列，就是从这个字符串中能够提取出的最长的回文子序列。
举个简单的例子，假设我们有字符串 "bbabcbab"，这个字符串的最长回文子序列是 "bab"。虽然不是连续的，但是它符合回文的条件。
二、如何求解？
一开始看到这个问题的时候，我也是有点懵逼的，感觉简单的回文问题怎么这么复杂？但其实，解决这个问题并不难，只要善用动态规划（DP）方法。
核心思路是：我们用一个二维数组 dp[i][j] 来表示字符串 s 从索引 i 到 j 之间的最长回文子序列的长度。具体的递推关系可以这么总结：
如果 s[i] == s[j]，那么dp[i][j] = dp[i+1][j-1] + 2。也就是说，当前的两个字符是相同的，它们可以被包括进来，所以下一层的解加2。如果 s[i] != s[j]，那么dp[i][j] = max(dp[i+1][j], dp[i][j-1])。也就是如果这两个字符不相等，那么我们就从两个子问题中取最大值，尝试跳过其中一个字符。
初始化的时候，dp[i][i] = 1，因为任何一个单独的字符都是回文的。
三、代码实现
下面我来给大家写一个 Python 代码实现：
def longestPalindromeSubseq(s: str) -> int:
n = len(s)
# 创建一个 n x n 的二维 dp 数组
dp = [[0] * n for _ in range(n)] # 初始化 dp 数组，每个单独字符的回文子序列长度为 1
for i in range(n):
dp[i][i] = 1
# 进行动态规划填充 dp 数组
# 从长度为 2 的子串开始，逐渐扩大到整个字符串
for length in range(2, n + 1): # length 是当前子串的长度
for i in range(n - length + 1): # i 是子串的起始位置
j = i + length - 1 # j 是子串的结束位置
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])
# 最终结果是整个字符串的最长回文子序列的长度
return dp[0][n-1]
四、复杂度分析
时间复杂度：O(n^2)。我们需要遍历整个二维数组 dp，而 dp 的大小是 n * n，因此时间复杂度是 O(n^2)。
空间复杂度：O(n^2)。由于我们使用了一个二维数组来存储状态，所以空间复杂度也是 O(n^2)。
五、注意事项
有朋友可能会问：“那么有没办法降低空间复杂度呢？”哈哈，当然有办法！我们可以通过优化空间，将二维数组优化成一维数组。因为计算 dp[i][j] 只和 dp[i+1][j]、dp[i][j-1] 以及 dp[i+1][j-1] 有关，所以只需要记录一行或者一列的状态，其余部分可以通过滚动数组来完成。这样可以将空间复杂度降到 O(n)。
但是要注意，动态规划的状态转移过程中，滚动数组可能会让代码稍显复杂，这就需要我们小心处理。
六、总结
说到底，求解最长回文子序列并不难，只要理解了动态规划的状态转移方程，就可以轻松解决。而且，掌握动态规划不仅有助于解决这类问题，还能帮助我们应对很多复杂的字符串问题。毕竟，程序员的世界里，动不动就碰到一堆字符串和数组，掌握好这些技巧，能够大大提高解题效率。
对编程、职场感兴趣的同学，大家可以联系我微信：golang404，拉你进入“程序员交流群”。
虎哥作为一名老码农，整理了全网最全《python高级架构师资料合集》。