Question

考点

算法-动态规划算法-动态规划算法

面5笔5

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

Answer 1

解答

运用的是动态规划的思想，由于是求最长回文字符串。

dp数组定义为：在子串s[i…j]中，最长回文子序列的长度为dp[i][j];

子问题：所以其子问题可以看作是求短一点长度，例如求dp[i][j],可以由求其子问题dp[i+1][j-1]的结果算出。所以其子问题即是长度减去左右两端的字符串的长度。

递推公式: dp[i][j] = dp[i+1][j-1] + 2 s[i] == s[j]

dp[i][j] = max(dp[i+1][j],dp[i][j+1]) s[i] != s[j]

getLength(str):
输入： 一个字符串
输出： 字符串内最长回文字符串的长度
for i <-- length - 1 to 0 do:
dp[i][i] = 1;
for j <-- i+1 to length -1 do:
If(str[i] == str[j]) then:
dp[i][j] = dp[i+1][j-1]+2;
else
dp[i][j] = max(dp[i+1][j],dp[i][j+1])
end
end
return dp[0][len-1];