查找 Python 中最长回文子序列长度的程序
假设我们有一个小写字符串 s;我们需要找出 s 中最长回文子序列的长度。
因此,如果输入如下 s = “aolpeuvekyl”,则输出将为 5,因为回文是 “level”。
为了解决此问题,我们将按照以下步骤操作 -
- n := s 的大小
- 定义函数 dp()。它将获取 i、j
- 如果 i 等于 j,则
- 返回 1
- 否则,当 i > j 时,则
- 返回 0
- 否则,
- 如果 s[i] 等于 s[j],则
- 返回 2 + dp(i + 1, j - 1)
- 否则,
- 返回 dp(i + 1, j) 和 dp(i, j - 1) 的最大值
- 如果 s[i] 等于 s[j],则
- 返回 dp(0, n - 1)
示例(Python)
让我们看看以下实现以获得更好的理解 -
class Solution: def solve(self, s): n = len(s) def dp(i, j): if i == j: return 1 elif i > j: return 0 else: if s[i] == s[j]: return 2 + dp(i + 1, j - 1) else: return max(dp(i + 1, j), dp(i, j - 1)) return dp(0, n - 1) ob = Solution() s = "aolpeuvekyl" print(ob.solve(s))
输入
"aolpeuvekyl"
Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.
输出
5
广告