题解 | #最长回文子序列# Python3
最长回文子序列
https://www.nowcoder.com/practice/82297b13eebe4a0981dbfa53dfb181fa
import sys
# dp[i][j] 为 从 i 到 j 的最长子序列
# dp[i][j] = max(dp[i+1][j-1] + 2*(s[i]==s[j]),dp[i][j-1], dp[i+1][j])
# 需要知道 dp[i+1][j-1]和dp[i][j-1]的值，说明填表方向是,第一维从n到i，第二维从0到j
# 这种填表方向可行
s = input().strip()
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for i in range(n-1,-1,-1):
for j in range(i+1,n):
dp[i][j] = max(dp[i+1][j-1]+ 2*int((s[i]==s[j])), dp[i][j-1], dp[i+1][j])
print(dp[0][-1])
投递数字马力等公司6个岗位
查看19道真题和解析
